Every turn-by-turn GPS route, every enemy that paths around a wall in a video game, and every packet that finds its way across a network relies on a graph-search algorithm doing the same basic job: finding the cheapest route between two points. Two algorithms dominate that job, and they are closely related rather than competitors from different eras. Dijkstra’s algorithm, published in 1959, guarantees the shortest path in any graph with non-negative edge weights. A*, published in 1968, is Dijkstra’s algorithm plus a heuristic that steers the search toward the goal — often visiting far fewer nodes along the way.
This guide explains how each algorithm actually works, what their complexity guarantees are, when A*’s heuristic helps and when Dijkstra is the only correct choice, and where each shows up in production systems.
At a Glance
| Algorithm | Time Complexity | When to Use |
|---|---|---|
| Dijkstra’s Algorithm (1959) | O(V²) with a simple array; O((V + E) log V) with a binary heap; Θ(E + V log V) with a Fibonacci heap | Non-negative weighted graphs, no usable sense of “direction” to the goal, or when you need shortest paths to every node from one source |
| A* Search (1968) | Same worst case as Dijkstra, but typically far fewer nodes expanded in practice; often described loosely as O(b^d) for branching factor b and solution depth d | Single-source, single-target searches where a cheap, reasonably accurate distance estimate (heuristic) to the goal exists, e.g. grid maps, road networks, puzzles |
Dijkstra’s Algorithm: Shortest Paths Without Guessing
Edsger W. Dijkstra described the algorithm in his short 1959 paper “A Note on Two Problems in Connexion with Graphs,” published in Numerische Mathematik (he said later that he designed it in 1956, without a computer, as a demonstration of what a new machine could do). The algorithm solves the single-source shortest path problem: given a starting node, find the cheapest path from it to every other reachable node.
The mechanism is a greedy expansion from the start node. Every node is given a tentative distance — zero for the start, infinity for everything else. At each step, the algorithm picks the unvisited node with the smallest tentative distance, marks it “settled” (its distance is now final), and relaxes its outgoing edges: for each neighbor, it checks whether going through the current node produces a shorter distance than what’s currently recorded, and updates it if so. The algorithm repeats until every reachable node is settled, or until the target is settled if you only need one destination.
The guarantee comes from a simple invariant: because edge weights are never negative, the next unvisited node with the smallest tentative distance can never later be beaten by a path through a node that hasn’t been settled yet. That invariant breaks the moment negative edge weights are allowed — which is why Dijkstra’s algorithm is undefined on graphs with negative edges (use Bellman-Ford or Johnson’s algorithm instead).
Implementation determines the running time. A naive array scan to find the minimum each time gives O(V²), where V is the number of vertices — fine for dense graphs. Replacing that linear scan with a binary heap (priority queue) brings it to O((V + E) log V), where E is the number of edges. A Fibonacci heap improves it further to Θ(E + V log V), which matters at very large scale but adds implementation complexity most teams don’t bother with.
A*: Dijkstra With a Sense of Direction
A* was introduced in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael of the Stanford Research Institute, in the paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” (IEEE Transactions on Systems Science and Cybernetics). Their goal was to prove, formally, when it’s safe to let a search use a “guess” about remaining distance to speed things up without sacrificing optimality.
A* expands nodes in order of f(n) = g(n) + h(n), where g(n) is the known cost from the start to node n, and h(n) is a heuristic estimate of the remaining cost from n to the goal. Dijkstra’s algorithm is the special case where h(n) = 0 for every node — it has no sense of which direction the goal is in, so it explores uniformly outward. A* uses h(n) to prioritize nodes that look like they’re heading toward the goal, which in practice means it expands a much smaller fraction of the graph before finding the answer.
The catch is that this speedup is only safe under specific conditions on the heuristic:
- Admissible: h(n) must never overestimate the true remaining cost from n to the goal, for every node n. An admissible heuristic guarantees A* finds the optimal (cheapest) path, because it never prematurely discards a path that could turn out to be the best one.
- Consistent (monotone): a stronger condition where, for every edge (x, y), h(x) ≤ cost(x, y) + h(y). A consistent heuristic is also admissible, and it guarantees that once A* settles a node, it never needs to revisit it — which is what makes A*’s practical running time so much better than Dijkstra’s in the cases it’s suited for.
On a 2D grid, straight-line (Euclidean) distance to the goal is always admissible, because no real path can be shorter than a straight line. Manhattan distance is admissible when movement is restricted to four directions. A heuristic that overestimates — for example, one that is miscalibrated to favor speed over correctness — can make A* run faster but can also return a suboptimal path, so it stops being “A*” in the formal sense and becomes a weighted or greedy variant.
Worked Example: Why the Heuristic Matters
Picture a road network as a grid, with a start point in the southwest corner and a destination in the northeast corner. Dijkstra’s algorithm expands outward from the start in all directions equally, like a flood fill — it has already explored the southeast and northwest regions before it even reaches the destination, because it has no information telling it those directions are wrong. A*, using straight-line distance to the destination as its heuristic, consistently favors nodes that reduce the remaining distance, so its search area looks more like a narrow cone pointed at the goal rather than a circle.
Both algorithms, given an admissible heuristic in A*’s case, return the same optimal path length. The difference is entirely in how many nodes had to be examined to get there — which is the whole reason A* exists.
A minimal pseudocode sketch of A*’s main loop:
open_set = {start}
g[start] = 0
f[start] = h(start, goal)
while open_set is not empty:
current = node in open_set with lowest f value
if current == goal:
return reconstruct_path(current)
remove current from open_set
for each neighbor of current:
tentative_g = g[current] + cost(current, neighbor)
if tentative_g < g[neighbor]:
g[neighbor] = tentative_g
f[neighbor] = tentative_g + h(neighbor, goal)
if neighbor not in open_set:
add neighbor to open_set
return failure // no path existsSet h(n) = 0 everywhere in this same loop and it is, exactly, Dijkstra’s algorithm.
Dijkstra vs A*: Side-by-Side
| Dimension | Dijkstra’s Algorithm | A* Search |
|---|---|---|
| Worst-case complexity | O(V²) naive; O((V+E) log V) with a binary heap | Same worst case as Dijkstra (it degrades to Dijkstra if h=0); typically much faster in practice with a good heuristic |
| Optimality guarantee | Always optimal, for non-negative edge weights | Optimal only if the heuristic is admissible |
| Heuristic required | None — it has no notion of a specific goal direction | Yes — requires an admissible (ideally consistent) heuristic function |
| Best suited for | Finding shortest paths to all nodes, or when no good distance estimate to a single goal exists | Single-target pathfinding where a cheap geometric or domain estimate to the goal is available |
| Typical use cases | Network routing protocols, all-pairs precomputation, graphs without spatial structure | GPS navigation, game AI pathfinding, robotics motion planning, puzzle solving |
Real-World Use Cases
Navigation and routing. Modern mapping engines rarely run textbook A* directly on raw road graphs — they use heavily optimized variants (such as contraction hierarchies) layered on the same core idea — but the underlying principle is A*’s: use geographic distance to the destination as a heuristic so the search doesn’t waste time exploring roads headed the wrong way.
Game AI. A* is the default pathfinding choice in game development because levels are usually grids or navigation meshes with an obvious, cheap heuristic (straight-line or Manhattan distance to a known target), and frame-time budgets reward an algorithm that minimizes nodes expanded.
Network routing. Classic link-state routing protocols compute shortest paths from a router to every other router in the network — a one-to-all problem with no single fixed “goal” and no obvious geometric heuristic, which is exactly Dijkstra’s use case rather than A*’s.
Robotics motion planning. A* and its many descendants (D*, D* Lite, Jump Point Search) are used to plan collision-free paths through known or partially known maps, again relying on distance-to-goal heuristics to keep search times low enough for real-time control.
Which Should You Use?
Use Dijkstra’s algorithm when you need shortest paths from one source to all other nodes, when there’s no meaningful heuristic (the graph isn’t spatial, or you have no cheap way to estimate remaining distance), or when correctness with zero tuning risk matters more than raw speed.
Use A* when you have a single, specific target and a heuristic you can prove is admissible — most commonly a geometric distance in a spatial map. The heuristic is the entire value proposition of A*; without a good one, it collapses to Dijkstra’s algorithm with extra bookkeeping overhead, so it’s rarely a good choice for non-spatial or oddly structured graphs where a trustworthy estimate is hard to construct.
If you’re working with other distributed or graph-shaped data problems, our explainers on CRDTs and Unicode internals for developers cover two other areas where getting the underlying model exactly right avoids subtle, hard-to-debug failures later.
Bottom Line
Dijkstra’s algorithm and A* are not rival algorithms so much as the same algorithm with and without a compass. Dijkstra, unmodified, is the safe default for one-to-all shortest paths and non-spatial graphs. A* is Dijkstra plus a heuristic that, as long as it’s admissible, never sacrifices correctness and usually buys a large practical speedup — which is why it quietly runs inside most of the pathfinding you interact with daily, from games to navigation apps.
FAQ
Is A* always faster than Dijkstra?
Not necessarily. A* is faster when its heuristic is informative (closely tracks real remaining distance). With a weak or uninformative heuristic, A* can expand almost as many nodes as Dijkstra, and with h(n) = 0 it is literally identical to Dijkstra.
What happens if A*’s heuristic is not admissible?
A* can still terminate and return a path, but it is no longer guaranteed to be the shortest one, because the search can settle a node too early based on an overly optimistic-looking total that turns out to be wrong. This variant is sometimes called “weighted A*” and is used deliberately in some applications to trade optimality for speed.
Can Dijkstra’s algorithm handle negative edge weights?
No. Dijkstra’s algorithm requires non-negative edge weights; its correctness proof depends on it. Graphs with negative edges need Bellman-Ford or, for repeated queries, Johnson’s algorithm.
Is A* a type of Dijkstra’s algorithm, or a separate algorithm?
Formally, Dijkstra’s algorithm is a special case of A* where the heuristic function h(n) is zero for every node. A* generalizes Dijkstra by adding a goal-directed heuristic term.
What’s a good heuristic for a grid-based game map?
Manhattan distance for four-directional movement, diagonal (Chebyshev) distance for eight-directional movement, and Euclidean distance for free movement — all are admissible for their respective movement models, which is why they’re the standard choices in game pathfinding tutorials.
Sources
- Dijkstra, E. W. (1959). “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik. Original paper (PDF)
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics. Paper (PDF)
- A* search algorithm — Wikipedia
- Dijkstra’s algorithm — Wikipedia
- Amit’s A* Pages (Red Blob Games / Stanford)
- Baeldung: Dijkstra’s Algorithm vs A* Pathfinding
Discover more from Software Online Review
Subscribe to get the latest posts sent to your email.
