How is Dijkstra algorithm better tham A* algorithm for finding shortest path?

Question

How is Dijkstra algorithm better tham A* algorithm for finding shortest path?

Answer 1

It is not better at finding the shortest path. As long as you have an admissible heuristic for A* it will find the shorted path quicker than Dijkstra's would.

And as Mehrad pointed out in the comments, A* degrades into Dijktras if you give it a heuristic function that returns 0.

The wikipedia article for A* has a ton of good information on all of this.

Answer 2

If you want to find the shortest paths from a given source node to all nodes in a graph Dijkstra is better than A* since Dijkstra covers the whole graph anyway if you don't stop at a specific target. In contrast to simple Dijkstra A* is a goal-oriented algorithms and therefore needs to know both source and target node. If you wanted to cover the whole graph with N nodes with an A* algorithm you basically have to run the algorithm N times from the source node.

Dijkstra might also be better for finding the shortest paths from a source node to many targets of the graph. Depending on the location of the targets (especially distance from the source), number of targets M, size of the graph, quality of the A* heuristic there will be some break-even point where running one Dijkstra is better or less performant than running M times the A* algorithm.

Edit: Inspired by Matthew's correct critical comment I rephrase a bit and add remarks:

• Dijkstra is not better in finding the shortest paths to all nodes than A*. Correct would be: It's not worse than A*.
• To find the shortest paths to all nodes with A* one would set the function which estimates the costs to the target node to zero (since there is no target node). Setting the function which estimates the costs to the target node to zero makes A* identical with Dijkstra; Dijkstra is a special case of A*. (It's questionable if one should call the algorithm still "A*" (and not simply "Dijkstra") if the function is set to zero, because having a non-zero function is the core of A*.)
• When we try to find the shortest path to all nodes, we could also say: Dijkstra is sufficient. The refinement of A* is not necessary and doesn't help us here.
• The last remark is also true for searching in a graph, for instance: Find the node marked with a specific flag which is closest to a given source node. Since you don't know the target in advance it's not possible to define a function which estimates the costs to the searched node, thus A* (in the narrower sense of a non-zero function) is not applicable.