How does Dijkstra's Algorithm and A-Star compare?
Dijkstra is a special case for A* (when the heuristics is zero).
Dijkstra:
It has one cost function, which is real cost value from source to each node: f(x)=g(x)
.
It finds the shortest path from source to every other node by considering only real cost.
A* search:
It has two cost function.
g(x)
: same as Dijkstra. The real cost to reach a nodex
.h(x)
: approximate cost from nodex
to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from nodex
should be greater than or equalh(x)
. It is called admissible heuristic.
The total cost of each node is calculated by f(x)=g(x)+h(x)
A* search only expands a node if it seems promising. It only focuses to reach the goal node from the current node, not to reach every other nodes. It is optimal, if the heuristic function is admissible.
So if your heuristic function is good to approximate the future cost, than you will need to explore a lot less nodes than Dijkstra.
What previous poster said, plus because Dijkstra has no heuristic and at each step picks edges with smallest cost it tends to "cover" more of your graph. Because of that Dijkstra could be more useful than A*. Good example is when you have several candidate target nodes, but you don't know, which one is closest (in A* case you would have to run it multiple times: once for each candidate node).