What is the difference between Dijkstra and A* (A-star)?

Difficulty: 6/10

graph search, heuristics, algorithm complexity

Dijkstra vs A*

Dijkstra uses only the known cost from the source, while A* adds a heuristic estimate of the remaining cost to the target. A* prioritizes nodes using f(n)=g(n)+h(n). With an admissible heuristic that never overestimates the remaining cost, A* can find an optimal path while often exploring substantially fewer nodes than Dijkstra.

javascript

1
Dijkstra is effectively A* with h(n)=0.
2
A* requires a useful heuristic for its performance advantage.
3
An admissible heuristic preserves optimality under standard conditions.
4
A* is widely used in pathfinding and navigation.
5
Dijkstra is preferable when there is no meaningful target-directed heuristic.

Scenario Questions

0-2 years experience

Follow-up Questions