At a Glance
| Algorithm | Guarantees Shortest Path? | Needs a Heuristic? | Typical Complexity (binary heap) | Common Use |
|---|---|---|---|---|
| Dijkstra’s Algorithm | Yes, with non-negative edge weights | No | O((V+E) log V) | One-to-all shortest paths; network routing protocols |
| A* Search | Yes, if the heuristic is admissible (and consistent, for efficient graph search) | Yes | Same worst-case bound as Dijkstra; typically far fewer node expansions in practice | One-to-one pathfinding with a known goal: game AI, robotics, puzzle solving |
| Contraction Hierarchies / Multi-Level Dijkstra (used by OSRM) | Yes | No runtime heuristic — relies on heavy offline preprocessing of the graph instead | Near-instant query time after preprocessing; preprocessing itself is expensive | Continent-scale GPS and road-network routing |
How Dijkstra’s Algorithm Works
Dijkstra’s algorithm finds the shortest path from a single source node to every other reachable node in a weighted graph with non-negative edge weights. It works greedily: maintain a running “tentative distance” for every node (infinity for all but the source, which starts at zero), and repeatedly pick the unvisited node with the smallest tentative distance, mark it visited, and “relax” its outgoing edges — that is, check whether reaching a neighbor through this node would beat the neighbor’s current best-known distance, and update it if so. Because non-negative weights mean distances can only grow as you add edges, once a node is marked visited its tentative distance is guaranteed final; the algorithm never needs to revisit it. A priority queue (min-heap) is what makes “pick the smallest tentative distance” efficient instead of a linear scan every step.
Time and Space Complexity
With a binary heap as the priority queue, Dijkstra’s algorithm runs in O((V+E) log V) time, where V is the number of vertices and E the number of edges — each vertex is extracted from the heap once (O(log V) each) and each edge can trigger one heap update (also O(log V) each). With a Fibonacci heap, the bound improves to O(E + V log V), a classical result from Fredman and Tarjan (1984); the Fibonacci heap’s amortized O(1) “decrease-key” operation removes the log factor from the edge-relaxation term, leaving the log factor only on the V heap-extraction operations. In practice, binary heaps are far more common in production code because of their simplicity and good cache behavior, even though Fibonacci heaps are asymptotically better for sparse graphs with many more edges than vertices. Space complexity for both is O(V + E), dominated by storing the graph and the distance/visited tracking structures.
A Minimal Dijkstra Implementation in Python
import heapq
def dijkstra(graph, source):
"""Return shortest distances from source to every reachable node.
graph: dict mapping node -> list of (neighbor, non_negative_weight) tuples
"""
distances = {source: 0}
visited = set()
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph.get(node, []):
if weight < 0:
raise ValueError("Dijkstra requires non-negative edge weights")
candidate = current_dist + weight
if candidate < distances.get(neighbor, float("inf")):
distances[neighbor] = candidate
heapq.heappush(heap, (candidate, neighbor))
return distances
if __name__ == "__main__":
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A"))
# {'A': 0, 'C': 1, 'B': 3, 'D': 4}
How A* Improves on Dijkstra
A* is Dijkstra’s algorithm with one addition: instead of ranking nodes purely by the known cost-so-far g(n), it ranks them by f(n) = g(n) + h(n), where h(n) is a heuristic estimate of the remaining cost from node n to the goal. This lets A* bias its search toward the goal instead of expanding outward uniformly in every direction, which is why A* so often explores dramatically fewer nodes than plain Dijkstra when a good heuristic is available and a specific target is known in advance.
Two formal properties of the heuristic determine what A* can guarantee. A heuristic is admissible if it never overestimates the true remaining cost to the goal — it’s an optimistic lower bound, and h(goal) = 0. An admissible heuristic guarantees A* returns an optimal (shortest) path. A heuristic is consistent (also called monotone) if, for every edge (x, y), h(x) ≤ cost(x, y) + h(y) — a form of the triangle inequality. Consistency is the stronger property: it guarantees that once A* finalizes a node’s cost, that cost is optimal and the node never needs to be re-expanded, which is what lets an efficient graph-search implementation safely use a closed list. On classic grid maps, common admissible-and-consistent heuristics are Euclidean distance (any movement allowed) or Manhattan distance (four-directional grid movement only).
On complexity: A*’s worst case is the same O((V+E) log V) bound as Dijkstra with a binary heap, since A* is essentially Dijkstra running on a reweighted version of the graph. The informal “O(b^d)” intuition sometimes cited for A* — where b is the branching factor and d is the depth of the shallowest solution — is a rough mental model for tree search, not a precise bound for graph search; the real-world payoff of A* comes from expanding far fewer nodes in practice with a good heuristic, not from a better worst-case guarantee.
Dijkstra vs A*
| Dijkstra | A* | |
|---|---|---|
| Search pattern | Expands outward from the source roughly uniformly in all directions | Biases expansion toward the goal using the heuristic |
| Needs a specific goal upfront? | No — naturally solves one-to-all | Yes — the heuristic requires knowing the target |
| Heuristic required | No | Yes (admissible for correctness; consistent for efficient re-expansion-free search) |
| Worst-case time complexity (binary heap) | O((V+E) log V) | Same worst-case bound; typically far fewer nodes expanded in practice |
Real-World Applications
A* is a staple of game AI pathfinding: NPC movement, unit pathing in strategy games, and navmesh-based navigation in 3D games commonly run A* (or a variant) over a grid or navigation mesh, where Euclidean or Manhattan distance to the target makes a cheap, admissible heuristic.
GPS and road-network routing is a more nuanced story, and it’s worth correcting a common assumption here: not every major routing engine actually runs A* under the hood. OSRM (the Open Source Routing Machine), one of the most widely used open-source routing engines, explicitly does not use A* as its core algorithm. According to OSRM’s own GitHub README, it offers two pre-processing pipelines instead: Contraction Hierarchies (CH) and Multi-Level Dijkstra (MLD), with the project stating “we recommend using MLD by default except for special use cases such as very large distance matrices,” where CH is favored instead. Both techniques work by heavily preprocessing the road graph offline — adding “shortcut” edges that skip over long chains of low-importance roads — so that at query time, a much smaller search (still fundamentally a form of Dijkstra, run over the pre-contracted graph) can return a shortest path in milliseconds across a continent-scale map. Plain Dijkstra or A* run directly on a raw, unprocessed road graph simply can’t hit that latency at that scale; the heavy lifting happens ahead of time, not per query.
Trade-offs
Use plain Dijkstra when you genuinely need distances to every node from a single source (one-to-all), or when no good heuristic is available. Use A* when you have a single, known target and a cheap, reliable heuristic — it will typically explore a small fraction of the nodes Dijkstra would, with no loss of optimality given an admissible heuristic. Use precomputed hierarchical methods like Contraction Hierarchies or Multi-Level Dijkstra when the graph is large and mostly static (a road network that changes rarely) and you need repeated queries answered in milliseconds — the upfront preprocessing cost pays for itself across the huge number of queries a mapping service handles.
Bottom Line
Dijkstra and A* solve the same core problem — shortest paths in a weighted graph — but A* is only strictly better when you have a known destination and a good, admissible heuristic; otherwise it degenerates to Dijkstra anyway (a heuristic that’s always zero makes A* identical to Dijkstra). For massive, mostly-static graphs like road networks, production routing engines increasingly skip both in their pure form and lean on precomputed speed-up techniques such as Contraction Hierarchies and Multi-Level Dijkstra, as OSRM’s own documentation confirms.
FAQ
Does A* always outperform Dijkstra?
Only when a good admissible heuristic exists and you’re searching for a single specific target. For one-to-all shortest paths, or when no reasonable heuristic is available, Dijkstra is the appropriate tool — and with a zero heuristic, A* simply becomes Dijkstra.
What happens if an A* heuristic isn’t admissible?
A* can return a suboptimal (not-shortest) path, because an overestimating heuristic can cause the algorithm to prune a node that actually lies on the true shortest path.
Do real GPS navigation apps use A*?
Not necessarily. OSRM, a major open-source routing engine, uses Contraction Hierarchies and Multi-Level Dijkstra instead of A*, precomputing shortcuts over the road graph so queries resolve in milliseconds. Other routing engines may use different techniques; A* is not a universal standard for production-scale road routing.
Can Dijkstra’s algorithm handle negative edge weights?
No. Dijkstra assumes non-negative weights because its correctness proof relies on distances only increasing as paths get longer. Graphs with negative edge weights need a different algorithm, such as Bellman-Ford.
Sources
- osrm-backend README (Contraction Hierarchies vs. Multi-Level Dijkstra) — GitHub/Project-OSRM: https://github.com/Project-OSRM/osrm-backend
- Dijkstra’s algorithm (complexity with binary heap and Fibonacci heap) — Wikipedia: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- A* search algorithm (admissible and consistent heuristics) — Wikipedia: https://en.wikipedia.org/wiki/A*_search_algorithm
