This site has eleven shortest paths entries now — 0-1 BFS, Dijkstra's Algorithm, Bellman-Ford, Floyd-Warshall, A* Search, the ALT Algorithm, Iterative Deepening A* (IDA*), Johnson's Algorithm, SPFA, Yen's Algorithm, and Suurballe's Algorithm — 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 eleven pages individually answer it, because each one reasonably assumes you already know you need it specifically. This guide sorts nine of the eleven — the ones that all answer "what's the single cheapest path" — by the questions that decide between them; the other two, Yen's Algorithm and Suurballe's Algorithm, each answer a different question entirely (see below) and sit outside that sort on purpose.
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.
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).
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.
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 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. 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.
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 (this site's 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) — cheaper than
Floyd-Warshall specifically when E is much smaller than V², a sparse road
network rather than a near-complete graph. On a dense graph the two are comparable or Floyd-Warshall
wins outright once per-edge and per-heap-operation constants are counted, and 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.
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.
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.
| Entry | Answers | Time | Negative 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 |
| 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 |
Every one of these nine 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 nine above are a free upgrade over it, only a necessary one once costs actually differ. 0-1 BFS sits exactly between those two extremes: costs aren't all identical, but they're restricted enough (0 or 1, nothing else) that a deque 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 nine 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, and IDA* 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.
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.