Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Shortest-Path Algorithm

This site has thirteen shortest paths entries now — 0-1 BFS, Dial's Algorithm, Dijkstra's Algorithm, Bellman-Ford, Floyd-Warshall, A* Search, the ALT Algorithm, Iterative Deepening A* (IDA*), Johnson's Algorithm, SPFA, Yen's Algorithm, Suurballe's Algorithm, and Vertex-Disjoint Shortest Paths — each built, verified, and explained on its own page. "Which shortest-path algorithm do I use" is probably the single most common question this whole site could answer, and none of the thirteen pages individually answer it, because each one reasonably assumes you already know you need it specifically. This guide sorts ten of the thirteen — the ones that all answer "what's the single cheapest path" — by the questions that decide between them; the other three, Yen's Algorithm, Suurballe's Algorithm, and Vertex-Disjoint Shortest Paths, each answer a different question entirely (see below) and sit outside that sort on purpose.

Cheapest question first: are all edge weights exactly 0 or 1?

Worth checking before anything else, because it's the one question that lets you skip a priority queue entirely. If every edge in the graph costs either 0 or 1 — a shared boundary or a free jump alongside an ordinary step — 0-1 BFS gets Dijkstra's exact guarantee from a plain deque, back down at BFS's O(V + E) instead of O((V + E) log V). A single edge costing anything else — 2, 7, or a negative number — breaks the two-tier argument the whole trick rests on, and one of the six general-purpose entries below is needed instead.

Still not 0/1, but bounded: Dial's Algorithm

0-1 BFS's restriction doesn't have to stop at two values. If every edge cost is a small non-negative integer bounded by some known constant C — not just 0 or 1, but nothing larger than, say, 5 or 20 — Dial's Algorithm generalizes the same discovery-order trick from a two-ended deque to a circular array of C + 1 buckets, trading Dijkstra's O(log V) heap operations for plain array indexing, at O(E + VC) total. The bound has to stay small relative to the graph, though — its own pitfalls measure the tradeoff tipping over on the same 77-cell demo grid both ways: a clear win at C = 4 (244 bucket operations against a linear-scan priority queue's 717), over 3x more total work than that same priority queue once C grows to 500. Reach for it when weights are bounded, small, non-negative integers; fall back to Dijkstra once C is large relative to V, or the weights aren't bounded integers at all.

Three more questions, not eight algorithms

Past that first check, in order, cheapest to check first: Can any edge be negative? If every edge cost is guaranteed non-negative, three of the remaining eight (Bellman-Ford, Johnson's, SPFA) are doing work you don't need and paying for it. Do you need distances from one source, or between every pair? All-pairs is a genuinely different, more expensive problem, not just "run the single-source version more." Is there a fixed goal, plus some cheap way to estimate remaining distance? Only relevant once the first question is already "no" — a heuristic only helps an algorithm that's allowed to trust it, and decides between Dijkstra and A*/ALT/IDA*; which of those three comes down to whether coordinates exist to build a heuristic from at all, and whether A*'s own open-set memory is itself the constraint (see below).

No negative edges: Dijkstra vs. A*

This is the common case — road networks, terrain costs, anything where "cost" is a real physical quantity — and Dijkstra's Algorithm is the default answer: O((V + E) log V) with a binary heap, always correct, no assumptions beyond non-negative edges. It explores outward evenly in every direction, with no notion of which way the goal actually is.

If there's a single fixed goal and a cheap way to estimate how far it still is — Manhattan distance on a grid, straight-line distance on a map — A* Search biases that same priority queue toward the goal and typically finalizes far fewer nodes to reach the identical answer, at the same O((V + E) log V) worst-case bound (a heuristic of zero degenerates A* into exactly Dijkstra). The trade is that the heuristic has to be admissible — never overestimate — or A* can report a path that costs more than the cheapest one exists and give no indication anything went wrong; A*'s own pitfalls work a case where a 2× Manhattan heuristic reports a path 22% more expensive than optimal. Reach for Dijkstra when there's no single fixed goal (find distances to everywhere) or no cheap admissible estimate available; reach for A* when both exist.

When even A*'s own frontier becomes the actual bottleneck — the open set can hold up to O(V) entries in the worst case, and for a state space large enough (or implicit, generated on the fly rather than stored up front) that's a real limit, not just an inconvenience — Iterative Deepening A* (IDA*) gets the identical worst-case correctness guarantee down to O(d) memory: just the current path, nothing else. It pays for that with real, repeated re-exploration once per iteration — its own Complexity section measures a 15.8x overhead over A* on a maze with several alternate routes to the same cell — so it's a genuine trade, not a strict upgrade. Reach for it when the underlying state space is shaped more like a tree than a graph (few or no convergent paths back to the same node — Korf's original sliding-tile puzzle is the classic case) and memory, not time, is what's actually running out.

Race them yourself

"Typically finalizes far fewer nodes" above is doing real work as a qualifier — it depends on where the goal sits, and the difference is stark enough to measure directly rather than take on faith. This runs the exact reference implementations from Dijkstra's Algorithm and A* Search, unmodified, on the same freshly generated weighted grid, and counts cells finalized (the same "visited" flag both algorithms already track internally) rather than timing — both are far too fast at these grid sizes for performance.now() to clear JIT noise in a single run, the same reason the search race counts array reads instead of milliseconds.

Press "Run race" to run both algorithms on a freshly generated grid.

Set start/goal to opposite corners and terrain to open field, and A* doesn't just do a little worse than usual — it finalizes exactly as many cells as Dijkstra, every time, at every grid size tested (400/400 at 20×20, 1,600/1,600 at 40×40, 6,400/6,400 at 80×80, measured over hundreds of trials each with zero exceptions). This isn't a rounding coincidence: with uniform cost and an exact Manhattan heuristic, every cell inside the rectangle spanning start and goal sits on some shortest path between them, so f = g + h is the same constant for all of them — A* has no basis to prefer any cell over any other until the whole rectangle is exhausted, and corner-to-corner on an open grid, that rectangle is the whole grid. A heuristic that never overestimates still has to be informative — actually distinguish cells by how promising they look — or it buys nothing.

Switch start/goal to goal a quarter-grid away — a more typical query, somewhere to look up a route rather than trace the map's full diagonal — and the same open terrain flips completely: A* finalizes roughly 14-17% of what Dijkstra does at every size tested (measured 121 vs. 820 at 40×40, 441 vs. 3,240 at 80×80). rough terrain narrows the gap in the corner-to-corner case (A* still wins, roughly 66-77% of Dijkstra's count depending on size, since the cost bumps break the exact-tie condition above) but the goal-nearby case stays A*'s biggest win regardless of terrain — roughly 25-56% of Dijkstra's count, a smaller edge than open terrain's 14-17% but still a real one at every size measured — the heuristic gets to matter again once "closer to the goal" and "cheaper so far" aren't perfectly redundant information the way they are on an open, corner-to-corner grid. Both algorithms agree on the total path cost in every trial across every combination above — they'd better, since they're solving the identical problem — so any mismatch shown above would mean a real bug, not an expected outcome.

A* needs a heuristic — ALT builds one with no coordinates

Both A* and IDA* still need something Dijkstra doesn't: a cheap, admissible estimate of the remaining distance, and that estimate has always come from coordinates so far — Manhattan distance on a grid, straight-line distance on a map. Plenty of real graphs don't have any: a citation graph, a dependency graph, a network where the edge weight is a toll or a latency with no embedding behind it. The ALT Algorithm builds an admissible heuristic anyway, from nothing but the graph's own edge weights — a one-time Dijkstra pass from a handful of landmark nodes, in both directions, turns the triangle inequality into a valid lower bound to any goal. The trade is upfront cost instead of upfront coordinates: preprocessing runs O(k · (V + E) log V) for k landmarks before the first query can use it, and ALT's own pitfalls show that cost only pays for itself once the same landmark table answers several queries against different goals — a single one-off query is cheaper run as plain Dijkstra outright. Reach for ALT specifically when A* would help but there's no map to build a heuristic from and the same graph will answer many shortest-path queries, not just one; reach for Dijkstra when there's no repeat-query case to amortize the preprocessing against.

Negative edges, one source: Bellman-Ford vs. SPFA

Negative edges break Dijkstra's and A*'s core invariant outright — a node popped as "finalized" can turn out not to be, once a negative edge further out makes some other route cheaper. Bellman-Ford is the safe default: relax every edge, V - 1 times, no assumption about which nodes are "done" until the very end, O(V · E). It also detects negative cycles as a side effect — if a full pass still finds an improvement after V - 1 passes, a negative cycle must be reachable from the source, and Bellman-Ford's detection flags every node reachable from that cycle, not just the nodes on it.

SPFA is the same idea with a work-queue instead of blindly re-scanning every edge every pass — only edges leaving a node whose distance just improved get re-examined — and it's frequently much faster in practice: SPFA's own measured sweep over random graphs found well over 150× fewer relaxation checks than Bellman-Ford's fixed (V − 1) × E on sparse, no-negative-edge graphs, shrinking to roughly 11–15× on dense graphs where nearly every edge is negative — never vanishing in that testing, but shrinking hard as density and negative-edge share both turn up together. The catch, worth taking seriously and not just as a footnote: SPFA's own pitfalls confirm its worst case is exactly Bellman-Ford's O(V · E), with adversarial graphs that force it to re-examine nearly as many edges, plus queue-bookkeeping overhead on top. It's a practical shortcut for the common case, not a strict improvement with a better worst-case guarantee — reach for it when the graph is large enough that Bellman-Ford's fixed pass count is a real, felt cost, and fall back to Bellman-Ford when a predictable, bounded amount of work matters more than typical-case speed.

Every pair, not just one source: Floyd-Warshall vs. Johnson's

Needing distances between every pair of nodes — a full routing table, not one source's distances — is a different problem, and running a single-source algorithm once no longer answers it. Floyd-Warshall is the simple answer: three nested loops, O(V³), independent of how many edges actually exist, so a dense graph and a sparse one with the same node count cost exactly the same. It handles negative edges (no negative cycle) for free, and detects a negative cycle by checking whether any node's own diagonal entry (dist[i][i]) went negative — which flags exactly the nodes sitting on the cycle, a narrower guarantee than Bellman-Ford's flood-filled reachable set; Floyd-Warshall's own pitfalls work through a case where a node downstream of a cycle keeps a deceptively unflagged diagonal of exactly zero.

Johnson's Algorithm answers the same question differently: one Bellman-Ford pass from a virtual source computes a potential for every node, that potential reweights every edge to be non-negative without changing which path is cheapest, and then plain Dijkstra runs once per node. Total cost is O(V² log V + V · E) with a Fibonacci heap — cheaper than Floyd-Warshall specifically when E is much smaller than V², a sparse road network rather than a near-complete graph — but that win belongs to the heap, not the algorithm by itself. This site's own array-backed reference implementation makes each of those V Dijkstra runs O(V² + E) instead (the same array-vs-heap trade Dijkstra's own page makes for its demo), and a V · (V² + E) total is Ω(V³) no matter how small E gets — never actually below Floyd-Warshall's flat O(V³). Measured directly: from V=50 to V=800, across edge counts from a bare E≈V up to a near-complete E≈V², Floyd-Warshall wins every single case, by roughly 1.3× on the sparsest graphs tested up to a flat 2× on dense ones — the array-backed version gets relatively worse as the graph gets sparser, the opposite of the textbook heap-based story. Reaching the real sparse-graph win needs an actual binary or Fibonacci heap backing each Dijkstra run; without one, Floyd-Warshall's O(V³) with no reweighting step is simply less to get wrong. Negative-cycle detection happens once, in Johnson's own Bellman-Ford phase — if it fires, Dijkstra never runs at all, since a non-converged potential would silently hand Dijkstra a graph that isn't actually non-negative.

A different question: K paths instead of one

Everything above answers "what's the single cheapest path" faster or under different constraints — none of it helps if the single cheapest path turns out to be unusable (a closed road, a link that's down) or if the actual need is backup capacity, not just one optimal route. Yen's Algorithm answers a genuinely different question: the K cheapest loopless paths, ranked. It isn't a replacement for anything above — it calls repeated restricted Dijkstra searches as its subroutine, so whichever single-source algorithm fits the graph's edge weights still has to run underneath it. Reach for it only when a ranked list of alternatives is the actual requirement; it costs a full extra pass of searches per additional path (see its own Complexity section), so asking for K paths when only the best one is ever used is paying for nothing.

A third question: a guaranteed-disjoint pair

Yen's own ranked list doesn't promise the second path avoids the first one's edges — on Suurballe's own demo graph the two cheapest paths overall share a real edge, which defeats the point if the actual need is a backup route that survives one link going down. Suurballe's Algorithm answers that narrower question directly: the two paths, source to target, with the lowest combined cost that share no edge at all. It isn't a ranked-list generalization of Yen's, and it isn't a replacement for Dijkstra either — it's two Dijkstra calls plus a reweighting pass, cheaper than Yen's despite the stricter guarantee, because it doesn't search once per candidate deviation. Reach for it specifically when the requirement is resilience — a real second route, not just a second-best number — and note it guarantees edge-disjoint paths, not vertex-disjoint ones; the two returned paths can still pass through the same intermediate node (see below for the fix when that matters).

A fourth question: vertex-disjoint, not just edge-disjoint

Suurballe's own guarantee is a real gap for a caller worried about a node failing, not just a link — a router going down, not a cable being cut. Vertex-Disjoint Shortest Paths answers that stricter question with no new search algorithm at all: split every node but the source and target into an in-copy and an out-copy joined by a zero-cost edge, so passing through a node and using that node's one edge become the same event, then run Suurballe's algorithm completely unmodified on the transformed graph. Same O((V + E) log V) bound, roughly double the nodes and edges to search. Reach for it instead of plain Suurballe specifically when the failure being planned against is a node, not just an edge; reach for plain Suurballe when edge-disjoint already covers the real failure mode, since the transform is pure overhead otherwise.

Side by side

EntryAnswersTimeNegative edges?Reach for it when
0-1 BFS single source, everywhere O(V+E) no, and only 0 or 1 every edge costs exactly 0 or 1, nothing else
Dial's Algorithm single source, everywhere O(E + VC) no, and bounded by C edge weights are small non-negative integers, bounded by a known C
Dijkstra single source, everywhere O((V+E) log V) no the general non-negative default, no single fixed goal
A* single source, single goal O((V+E) log V), fewer nodes visited in practice no fixed goal + a cheap admissible distance estimate
ALT single source, single goal (many, once preprocessed) O(k·(V+E) log V) preprocess, then O((V+E) log V) per query no A* would help but there's no map — and many queries to amortize preprocessing
IDA* single source, single goal same worst case as A*, O(d) memory no A*'s own memory is the constraint, tree-like state space
Bellman-Ford single source, everywhere O(V·E) yes, and detects cycles (flags reachable set) negative edges, predictable bounded work matters
SPFA single source, everywhere O(V·E) worst case, often much less yes, and detects cycles (existence only) negative edges, graph large enough that typical-case speed matters
Floyd-Warshall every pair O(V³) yes, and detects cycles (flags nodes on the cycle) all-pairs, any density, simplicity over squeezing out constants
Johnson's every pair O(V² log V + V·E) yes, and detects cycles (aborts before Dijkstra runs) all-pairs, sparse graph — E well below V²
Yen's single source, single goal, K ranked paths O(K·V·(V+E) log V) no (subroutine-dependent) need a ranked list of alternatives, not just the one best route
Suurballe's single source, single goal, a disjoint pair O((V+E) log V) no need a genuine backup route, guaranteed to share no edge with the first
Vertex-Disjoint Shortest Paths single source, single goal, a vertex-disjoint pair O((V+E) log V) on a ~2x-sized graph no the backup route needs to survive a node failing, not just a link

What all ten assume, and the three that don't

Every one of these ten is doing more work than breadth-first search, and for the same reason: BFS's guarantee — the first path discovered is the shortest one — only holds because every edge secretly costs exactly 1. The moment edges have different costs, "discovered earliest" and "cheapest so far" stop being the same ordering, and Dijkstra's whole mechanism (a priority queue instead of a plain FIFO queue, or in IDA*'s case a series of bounded depth-first passes standing in for one) exists to track the ordering that still gives a correctness guarantee. If every edge genuinely costs the same, BFS is still the right tool — none of the ten above are a free upgrade over it, only a necessary one once costs actually differ. 0-1 BFS and Dial's Algorithm both sit between those two extremes: costs aren't all identical, but they're restricted enough (0 or 1 for the former, any small bounded integer for the latter) that array indexing recovers the same discovery-order trick BFS uses, without paying for either a priority queue or IDA*'s repeated re-exploration.

And none of the ten define what "shortest path" even means once a negative cycle sits between the source and a node in question — walking the cycle one more time always shrinks the total, without limit. Dijkstra, A*, ALT, IDA*, and Dial's Algorithm don't detect this at all, silently trusting it can't happen — ALT inherits it doubly, once from the plain Dijkstra its own search is built on, and once again from the landmark-preprocessing Dijkstra runs a negative cycle would just as silently corrupt; the other four detect it and stop, at increasingly narrow granularity (Bellman-Ford's whole reachable set, down to Johnson's blunt all-or-nothing abort) rather than reporting a number for the undefined case. Suurballe's Algorithm sidesteps the question by construction — it's built directly on top of one non-negative-safe Dijkstra call, so it inherits Dijkstra's silent trust that no negative edge exists rather than detecting one. Vertex-Disjoint Shortest Paths inherits that same trust a second time over, being nothing but a graph transform sitting in front of the identical, unmodified Suurballe call.

This is the site's second guide, following the same pattern as its first: a cross-cutting page comparing existing entries instead of adding a new algorithm, for a family that had grown large enough (six entries) that "which one do I use" is a real question a reader would have. See the journal for this session's notes.