On this page

Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson & A*

Why this exists

A weighted graph assigns a number to every edge — a distance in metres, a latency in milliseconds, a toll, a log-probability, a cost. "What is the cheapest way to get from here to there?" is then the shortest path problem, and it is one of the most heavily used computations in software. Every link-state router on the internet runs it when the topology changes. Every maps application runs it, or a preprocessed descendant of it, when you ask for directions. Game engines run it for every unit that has to walk around a wall. Compilers, chip routers, currency-arbitrage detectors, spell checkers (edit distance is a shortest path on a grid) and min-cost-flow solvers all reduce to it.

There is no single best algorithm, because the right answer depends on three questions. Are weights non-negative? If yes, Dijkstra's greedy algorithm (1959) finalizes vertices in increasing order of distance and runs in . If some weights are negative, greedy finalization is wrong, and you need Bellman-Ford (Bellman 1958, Ford 1956, Moore 1959), which is slower, , but also detects negative cycles — loops whose total weight is negative, around which "shortest" stops being defined. One source or all pairs? For all pairs on a dense graph, Floyd-Warshall (1962) is three nested loops; for all pairs on a sparse graph with negative edges, Johnson's algorithm (1977) uses one Bellman-Ford run to reweight the edges so that Dijkstra becomes valid. Is there a target and a sense of direction? A* (Hart, Nilsson and Raphael, 1968) is Dijkstra steered by a heuristic estimate of the remaining distance, and on a grid with an open sky it can expand 50 times fewer nodes.

The Graphs overview gives one implementation of each of the three classics and a comparison table. This lesson proves each one, measures A* against Dijkstra, recovers negative cycles, reweights with potentials, and ends with a decision table.

Pattern triggers

If the problem says or has……think of
"minimum time / cost / distance", weights all Dijkstra with a binary heap
Every edge has the same weightBFS — see BFS in Depth
Weights are only 0 and 1 (e.g. "free move" vs "costly move")0-1 BFS with a deque
Some weights negative, single sourceBellman-Ford
"Detect whether profit can grow forever", "arbitrage", "infinite loop of gain"Negative-cycle detection (Bellman-Ford round , or Floyd-Warshall diagonal)
"Shortest distance between every pair", or soFloyd-Warshall
"Is u reachable from v?" for all pairsTransitive closure (Floyd-Warshall with booleans)
All pairs, sparse graph, negative edgesJohnson: Bellman-Ford once, then Dijkstra from every vertex
Graph is a DAG (dependencies, time-ordered events)Topological-order DP, negative edges fine — see Topological Sort
Single source and target on a grid or map, geometry knownA* with Manhattan / octile / Euclidean heuristic
"At most k stops / k edges"Bellman-Ford limited to k+1 rounds, or a layered graph
"Using at most one coupon / discount / wall break"Layered state graph (vertex, used) + Dijkstra
"Number of shortest paths"Dijkstra plus counting on the shortest-path DAG
"Second shortest", "k shortest routes"Pop each vertex up to k times (walks), or Yen's algorithm (simple paths)
"Minimize the maximum edge on the path" (effort, bottleneck)Dijkstra with max instead of +, or MST
"Maximize the probability" (product of edge probabilities)Dijkstra with max and *, or weights

Intuition & first principles

Let be the weight of edge and the true shortest distance from to (the minimum total weight over all paths, if is unreachable). Every algorithm in this lesson keeps an estimate dist[v] that starts at (and 0 for ) and only ever goes down. The single operation that lowers it is relaxation:

relax(u, v):
    if dist[u] + w(u, v) < dist[v]:
        dist[v] = dist[u] + w(u, v)
        parent[v] = u

Read it as: "I know a way to reach costing dist[u]; following the edge to costs dist[u] + w(u, v); if that beats the best way I know to , remember it."

Three facts make relaxation enough.

  1. Upper-bound property. dist[v] is always the length of some actual walk from to (or ), so dist[v] at all times. Relaxation never undershoots.
  2. Triangle inequality. True distances satisfy for every edge: going to optimally and then taking the edge is a way to reach . So once all distances are correct, no edge can be relaxed. Conversely, if no edge can be relaxed and dist is an upper bound with dist[s] = 0, then dist is exact (follow a true shortest path edge by edge; each edge satisfies the inequality, so by induction dist never exceeds along it).
  3. Optimal substructure. Any prefix of a shortest path is itself a shortest path. If is shortest to , then its part is shortest to — otherwise swap in the shorter one. So the parent pointers form a shortest-path tree rooted at , and reconstructing a path means following parent from the target back to .

The algorithms differ only in which edges they relax, and in what order. Relax in a bad order and you need many passes; relax in exactly the right order and one pass suffices. A topological order is the perfect order for a DAG. For a general graph with non-negative weights, the perfect order is "in increasing order of distance" — that is Dijkstra. Without non-negativity there is no cheap perfect order, so Bellman-Ford relaxes everything, repeatedly, until nothing changes.

Negative cycles are why that last case is hard. If a cycle has and is reachable from and can reach , then going around it once more always lowers the cost, so : no shortest walk exists. (A shortest simple path still exists, but finding it is NP-hard, because it would solve Hamiltonian path.) Every correct algorithm for negative weights therefore either assumes no negative cycles or reports them.

Mechanics

Dijkstra's algorithm

Maintain a set of settled vertices whose distance is final. Repeatedly settle the unsettled vertex with the smallest dist, and relax its out-edges. With a binary heap you do not need a "decrease key" operation: push a new (dist, vertex) entry every time a distance improves, and when you pop an entry whose key is larger than the vertex's current dist, skip it as stale. This is lazy deletion.

dist[v] = inf for all v; dist[s] = 0; pq = [(0, s)]
while pq:
    d, u = pop_min(pq)
    if d > dist[u]: continue                 # stale entry: u already settled with a smaller d
    for each edge u -> v with weight w:
        if d + w < dist[v]:
            dist[v] = d + w; parent[v] = u
            push(pq, (dist[v], v))
flowchart TD
    I["dist[s] = 0, push (0, s)"] --> L{"heap empty?"}
    L -->|"no"| P["pop smallest (d, u)"]
    P --> S{"d > dist[u]?"}
    S -->|"yes: stale"| L
    S -->|"no: settle u"| R["relax every edge u -> v"]
    R --> U{"d + w < dist[v]?"}
    U -->|"yes"| PU["set dist[v] and parent[v], push v"]
    U -->|"no"| L
    PU --> L
    L -->|"yes"| D["done: dist and parent are final"]

The running example is a directed graph with six vertices: S→A 4, S→B 1, B→A 2, A→C 1, B→C 5, A→D 6, C→D 3, C→T 6, D→T 2.

flowchart LR
    S((S)) -->|"4"| A((A))
    S -->|"1"| B((B))
    B -->|"2"| A
    A -->|"1"| C((C))
    B -->|"5"| C
    A -->|"6"| D((D))
    C -->|"3"| D
    C -->|"6"| T((T))
    D -->|"2"| T
Dijkstra always settles the closest unsettled vertex; with lazy deletion, outdated heap entries are simply skipped when they surface.

Trace: Dijkstra from S

Values from the trace generator scripts/traces/dijkstra.py. The dist column lists S A B C D T.

StepPopActiondist (S A B C D T)Heap after
0—init0 ∞ ∞ ∞ ∞ ∞(0,S)
1(0,S)settle S; A = 4, B = 10 4 1 ∞ ∞ ∞(1,B) (4,A)
2(1,B)settle B; A: 4 → 3, C = 60 3 1 6 ∞ ∞(3,A) (4,A) (6,C)
3(3,A)settle A; C: 6 → 4, D = 90 3 1 4 9 ∞(4,A) (4,C) (6,C) (9,D)
4(4,A)stale (dist[A] = 3), skipunchanged(4,C) (6,C) (9,D)
5(4,C)settle C; D: 9 → 7, T = 100 3 1 4 7 10(6,C) (7,D) (9,D) (10,T)
6(6,C)stale, skipunchanged(7,D) (9,D) (10,T)
7(7,D)settle D; T: 10 → 90 3 1 4 7 9(9,D) (9,T) (10,T)
8(9,D)stale, skipunchanged(9,T) (10,T)
9(9,T)settle T; no out-edges0 3 1 4 7 9(10,T)
10(10,T)stale, skipunchangedempty

Ten pushes (the source plus one per edge, since every edge improved a distance when relaxed); four of them went stale. Settling order S, B, A, C, D, T is increasing in distance (0, 1, 3, 4, 7, 9), as the correctness proof says it must be. Parent pointers give the path S → B → A → C → D → T with cost , even though it uses five edges and the direct-looking S → A → D → T costs 12.

Lazy deletion vs decrease-key

Textbook Dijkstra uses a priority queue with decrease-key: each vertex has one entry, and an improvement lowers its key in place. The heap then never holds more than entries, and the cost is pops plus decrease-keys, with a binary heap, or with a Fibonacci heap (Fredman and Tarjan, 1987), whose decrease-key is amortized.

Lazy deletion pushes up to entries instead, so the heap can grow to and each operation costs . Since , , so the bound is still ; the memory overhead is entries instead of . In exchange you use the standard library heap as is (Python's heapq, Java's PriorityQueue, C++'s std::priority_queue have no decrease-key), there is no position index to maintain, and the inner loop is simpler. Measured comparisons generally favour the lazy version in practice: a 2007 University of Texas study (Chen, Chowdhury, Ramachandran, Lan Roche, Tong, "Priority Queues and Dijkstra's Algorithm") found that heaps without decrease-key were usually faster than heaps with it, and Fibonacci heaps slowest, on the graphs they tested.

The array version for dense graphs

Drop the heap. Keep dist in a plain array, and each round scan all unsettled vertices for the minimum: rounds × scan relaxations . On a complete graph, , so the heap version costs and the array version wins by a factor and by cache-friendly sequential scans. Rule of thumb: if is close to (adjacency matrix input, a few thousand), use the array version. Prim's MST algorithm has the same dense variant for the same reason (Minimum Spanning Trees).

Path reconstruction

Store parent[v] whenever dist[v] improves. After the run, the path to is t, parent[t], parent[parent[t]], …, s, reversed. This costs per query and memory for the whole tree, much less than storing a path per vertex. If is unreachable, dist[t] is still and parent[t] was never set: check that before walking. If you need all shortest paths, keep every predecessor with dist[u] + w(u, v) == dist[v]; those edges form the shortest-path DAG, and counting or enumerating paths is a DAG DP on it.

Why negative edges break Dijkstra

Dijkstra settles believing no future path can reach more cheaply, because any future path leaves the settled set through some vertex whose distance is already dist[u], and edges can only add. One negative edge breaks the "can only add".

Counterexample: S→A 2, S→B 3, B→A -2, A→T 1.

flowchart LR
    S((S)) -->|"2"| A((A))
    S -->|"3"| B((B))
    B -->|"-2"| A
    A -->|"1"| T((T))

Dijkstra with a "settled" flag pops S, then A at distance 2 and settles it, relaxes A→T to 3, pops B at 3, finds B→A would give A distance 1 — but A is settled, so the improvement is ignored (or, if applied, never propagated to T). Result: A = 2, T = 3. Truth: S→B→A costs 1 and S→B→A→T costs 2. Running both versions confirms: settled-flag Dijkstra gives [0, 2, 3, 3] for S, A, B, T; Bellman-Ford gives [0, 1, 3, 2].

A subtlety interviewers like: the lazy-deletion code above has no settled flag. When B lowers dist[A] to 1, it pushes (1, A), A gets popped again and re-relaxes T to 2. So this particular implementation returns the right answer on graphs with negative edges but no negative cycles. The price is that vertices can be settled many times, and in the worst case the number of re-settlements is exponential in (this was shown by Johnson in 1973 for the re-insertion variant). On a graph with a negative cycle it loops forever. "Dijkstra works with negative edges if you allow re-insertion" is technically true and practically a trap; use Bellman-Ford or reweight with Johnson's potentials.

Bellman-Ford

Relax every edge, in any order; repeat times. A shortest path without negative cycles is simple, so it has at most edges, and round makes its -th edge correct (proof below). Stop early if a round changes nothing.

dist[v] = inf for all v; dist[s] = 0
for round = 1 .. V - 1:
    changed = false
    for each edge (u, v, w):
        if dist[u] != inf and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w; parent[v] = u; changed = true
    if not changed: break
for each edge (u, v, w):                         # round V: detection
    if dist[u] != inf and dist[u] + w < dist[v]: negative cycle reachable from s

The example below has two negative edges (B→A -3, C→D -1) and no negative cycle. The edges are scanned in the deliberately bad order D→E, C→E, C→D, B→D, A→C, B→A, S→B, S→A, so information travels only one edge per round.

flowchart LR
    S((S)) -->|"4"| A((A))
    S -->|"5"| B((B))
    B -->|"-3"| A
    A -->|"2"| C((C))
    B -->|"6"| D((D))
    C -->|"-1"| D
    C -->|"5"| E((E))
    D -->|"1"| E
Each round fixes at least one more edge of every shortest path, so V − 1 rounds always suffice, and a round that still improves something proves a negative cycle.

Trace: Bellman-Ford from S

Values from scripts/traces/bellman_ford.py. Updates are listed in the order they happen within the round.

RoundUpdates in scan orderdist after round (S A B C D E)
0init0 ∞ ∞ ∞ ∞ ∞
1B = 5, A = 40 4 5 ∞ ∞ ∞
2D = 11, C = 6, A: 4 → 20 2 5 6 11 ∞
3E = 12, E: 12 → 11, D: 11 → 5, C: 6 → 40 2 5 4 5 11
4E: 11 → 6, D: 5 → 30 2 5 4 3 6
5E: 6 → 40 2 5 4 3 4
6none — converged, no negative cycle0 2 5 4 3 4

The shortest path to E is S → B → A → C → D → E, cost , five edges, so it needs all rounds in this edge order. Scanning the same edges in the opposite order (S→A, S→B, B→A, A→C, B→D, C→D, C→E, D→E, a topological order of this DAG) finishes all distances in round 1 and confirms them in round 2. Edge order changes the number of rounds, never the answer, and never the worst-case bound.

Negative cycles: detect and recover

If round still relaxes some edge, a negative cycle is reachable from . To print it, remember the last vertex relaxed in round , then follow parent from times; you are now guaranteed to be standing on the cycle (the parent chain from leads back into it within steps). From there, follow parent until you return, and reverse.

Add the edge E→B -1 to the example. The cycle B → A → C → D → E → B now has weight . Bellman-Ford still relaxes in round 6; walking parents recovers the cycle as A → C → D → E → B → A, the same cycle starting elsewhere.

To detect a negative cycle anywhere in the graph (not just reachable from ), add a virtual source with a 0-weight edge to every vertex, or equivalently initialize dist[v] = 0 for every . That is what CSES "Cycle Finding" needs.

To find which vertices have : every vertex relaxed in round or later is either on a negative cycle or reachable from one; BFS/DFS from all of them marks the full set. A common exam/contest twist ("High Score") asks for the longest path from 1 to : negate weights, run Bellman-Ford, and answer "infinite" only if a vertex with distance is both reachable from 1 and can reach . Cycles elsewhere do not matter.

SPFA, and why its worst case is still

Most edges relaxed in a Bellman-Ford round do nothing, because dist[u] did not change since the last round. The Shortest Path Faster Algorithm (SPFA, popularized by Duan Fanding in 1994; the queue-based idea goes back to Moore's 1959 formulation) relaxes only out-edges of vertices whose distance changed, using a FIFO queue and an in-queue flag:

dist[s] = 0; queue = [s]; inq[s] = true
while queue:
    u = queue.pop_front(); inq[u] = false
    for each edge u -> v:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if not inq[v]: queue.push_back(v); inq[v] = true

On random graphs it is fast: on a random graph with 1,000 vertices and about 2,000 edges, a script counted 1,079 queue pops — barely more than one per vertex. But the worst case is unchanged: with a FIFO queue, the queue processes vertices in "waves" equivalent to Bellman-Ford rounds, and there can be of them, each touching edges. A simple construction triggers it: vertices , edges with weight added in decreasing order of , and a chain of weight 1. Each vertex starts with a bad direct-edge distance and is then improved once per wave as the chain propagates. Measured:

EdgesSPFA queue pops (crafted input)SPFA pops (random graph, same size)
1001974,951108
1,0001,997499,5011,079
2,0003,9971,999,0012,178

The crafted input costs pops: quadratic, i.e. for this sparse graph, the same as Bellman-Ford. Contest problem setters know this, and anti-SPFA tests (often grid-shaped graphs with crafted weights) are common in modern problem sets. The safe rules: use Dijkstra whenever weights are non-negative (SPFA is never a better choice there), and when weights are negative, treat SPFA as Bellman-Ford with a good average case, not as a different complexity class. For negative-cycle detection, SPFA needs a counter: if any vertex is enqueued times (or its path length reaches edges), there is a negative cycle.

Floyd-Warshall

All-pairs shortest paths by dynamic programming over the set of allowed intermediate vertices. Let be the shortest path whose intermediate vertices all lie in . Then (0 on the diagonal, for non-edges) and

— either the best path avoids vertex , or it passes through exactly once (a shortest path is simple), splitting into an part and a part that use only smaller intermediates. The table can be updated in place, so the whole algorithm is:

d = weight matrix (0 on diagonal, inf where no edge)
for k in 0 .. V-1:          # k MUST be the outer loop
    for i in 0 .. V-1:
        for j in 0 .. V-1:
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]; nxt[i][j] = nxt[i][k]

time, memory. For that is inner iterations — under a second in C++ or Java, several seconds in pure Python (NumPy can vectorize the two inner loops).

Trace: Floyd-Warshall on four vertices

Edges 0→1 3, 0→2 8, 1→2 -2, 1→3 1, 2→3 2, 3→0 2. Changes per phase (computed by script):

Phase (via )Entries that improve
: ∞ → 5 (3→0→1), : ∞ → 10
: 8 → 1 (0→1→2), : ∞ → 4, : 10 → 3
: 4 → 3 (0→1→2→3), : 1 → 0
: ∞ → 2, : ∞ → 4, : ∞ → 7

Final matrix (row , column ):

0123
00313
120-20
24702
32530

Negative cycles on the diagonal. starts at 0 and can only go below 0 if some walk has negative weight. After the algorithm, the graph has a negative cycle iff some , and is truly iff some with is reachable from and reaches (cp-algorithms' formulation: set when , and ). Adding the edge 3→1 -5 to the example creates the cycle 1→3→1 of weight , and the code below detects it.

Transitive closure. Replace min/+ with or/and: reach[i][j] |= reach[i][k] and reach[k][j]. This is Warshall's 1962 algorithm. With rows stored as bitsets, the inner loop becomes "if reach[i][k], then reach[i] |= reach[k]", which is .

Johnson's algorithm

For all pairs on a sparse graph with negative edges, runs of Bellman-Ford cost and Floyd-Warshall . Johnson gets by making all weights non-negative without changing which paths are shortest, then running Dijkstra from every vertex.

The trick is a potential and the reweighting

For any path the potentials telescope: . Every path is shifted by the same amount , so the ranking of paths is unchanged and shortest paths stay shortest. Cycles () are not shifted at all, so negative cycles are preserved, which is how Johnson detects them.

To make : add a new vertex with 0-weight edges to every vertex, run Bellman-Ford from , and set . The triangle inequality is exactly . Then run Dijkstra from each with and convert back: .

On the four-vertex example: , and the reweighted edges are 0→1 3, 0→2 10, 1→2 0, 1→3 1, 2→3 0, 3→0 2 — all non-negative. Dijkstra from 0 under finds (via 1), and , matching Floyd-Warshall.

The same reweighting keeps reduced costs non-negative in min-cost flow (Network Flow) and drives A*, as the next section shows.

Dijkstra explores in growing circles around ; if you only want one target , most of that circle is wasted. A* orders the heap by , where is the best known distance from (Dijkstra's dist) and is a heuristic estimate of the remaining distance . The search leans towards the target and stops when is popped.

  • is admissible if it never overestimates: . Then A* returns an optimal path, provided it is allowed to reopen (re-settle) a vertex when a cheaper is found later.
  • is consistent (monotone) if for every edge and — the triangle inequality for . Consistent implies admissible (sum the inequality along a shortest path to ), and with a consistent heuristic no vertex is ever reopened: the first time a vertex is popped, its is optimal. Proof below; the one-line reason is that A* with a consistent is Dijkstra on the Johnson-reweighted graph .
  • is consistent and turns A* into Dijkstra. The closer is to the true remaining distance, the fewer vertices A* expands; expands only vertices on a shortest path.

Grid heuristics, with , the absolute coordinate differences to the target:

Movement modelStep costsHeuristicFormulaConsistent?
4-neighbour1ManhattanYes, and exact on an empty grid
8-neighbourstraight 1, diagonal 1ChebyshevYes
8-neighbourstraight 1, diagonal OctileYes, exact on an empty grid
Any directionEuclidean lengthEuclideanYes, but weak on 4-/8-neighbour grids
8-neighbouras aboveManhattanNo — overestimates diagonals; paths can be suboptimal

Measured on a grid with 25% random walls (seed 1, start top-left, target bottom-right, ties broken towards larger , corner-cutting forbidden), counting vertices expanded (popped and settled) before the target is popped:

MovementDijkstra ()A*, EuclideanA*, best heuristicPath cost
4-neighbour7,5226,509924 (Manhattan)200
8-neighbour7,5224,9444,115 (octile)170.953
4-neighbour, no walls10,201—201 (Manhattan)200

All searches return the same path cost; the heuristic changes only the work. On the open grid Manhattan is exact, and A* expands exactly the 201 vertices of one shortest path, 50 times fewer than Dijkstra, which expands the whole grid. With walls, the gain shrinks because the heuristic ignores obstacles. Tie-breaking matters a lot on grids, where many vertices share the same : breaking ties towards larger (deeper nodes) is what gets the 201; breaking them arbitrarily can expand far more.

Road routers strengthen the heuristic with landmarks (ALT: lower bounds from precomputed distances to a few landmark vertices via the triangle inequality) or switch to contraction hierarchies (see Real-world uses).

k shortest paths and "at most k edges"

At most edges ("k stops"). Run Bellman-Ford for exactly rounds (for edges; edges for " stops"), but relax from a copy of the previous round's distances. Otherwise an edge relaxed early in a round can feed another edge later in the same round, and one round may extend a path by several edges. Equivalently, build a layered graph with vertices = "at having used edges", edges , and run any shortest-path algorithm on it; with non-negative weights, Dijkstra on the layered graph costs . The layered-state idea generalizes to "at most one discount", "at most wall breaks", "state = (vertex, fuel)".

k shortest walks (repeated vertices allowed): run Dijkstra but allow each vertex to be popped up to times; the -th pop of is the -th shortest walk. . CSES "Flight Routes" is this.

k shortest simple paths: Yen's algorithm (Yen, 1971). Find the shortest path . To get , for each vertex (the "spur node") on , take the root path , temporarily delete the edges that leave along any already-found path sharing that root, delete the root's vertices other than , and run Dijkstra from to . Each root + spur path is a candidate; the cheapest unused candidate is . That is up to Dijkstra runs per path: . On the running example, the three cheapest simple S → T paths cost 9 (S B A C D T), 10 and 10 (S A C D T and S B A C T) — the code below checks this.

Eppstein's algorithm (1998, SIAM Journal on Computing 28(2)) finds the shortest walks in after one Dijkstra, using a heap of "sidetrack" edges. Use it when is large and repeated vertices are acceptable; for simple paths, Yen and its refinements remain standard.

The ladder: brute force → better → optimal

The single-source, non-negative-weight case, climbed rung by rung.

Rung 1: enumerate all simple paths

DFS from , try every simple path, keep the cheapest to each vertex. Correct for any weights (no negative cycles) but the number of simple paths explodes: a complete graph on vertices has more than simple paths between two fixed vertices. is already billions.

Rung 2: Bellman-Ford

Relax all edges times: . Why it improves: it never enumerates paths. Relaxation shares work between all paths that pass through the same vertex — the optimal-substructure property turned into an algorithm. It also handles negative edges, which makes it the right answer whenever they exist.

Rung 3: Dijkstra with an array

If weights are non-negative, the vertex with the smallest tentative distance is already final, so relax each vertex's edges exactly once, in increasing order of distance: . Why it improves: each edge is relaxed once instead of times; the term is the cost of finding the minimum by scanning.

Rung 4: Dijkstra with a binary heap

Find the minimum with a heap instead of a scan: . Why it improves: for sparse graphs (, e.g. road networks with average degree under 4) this is instead of — for , about heap steps instead of scans. For dense graphs it is worse than rung 3; keep both.

With a single target, A* with a consistent heuristic expands a subset of what Dijkstra expands (often a small one). With many queries on a fixed graph, preprocessing (contraction hierarchies) makes each query far cheaper. Why it improves: it stops exploring in directions that cannot be on the answer, or precomputes the work that queries share.

Comparison

AlgorithmWeightsProblemTimeSpaceNegative cycles
Enumerate pathsanysingle sourceexponential—
BFSunitsingle sourcen/a
0-1 BFS0 or 1single sourcen/a
DAG DPany, DAG onlysingle sourceimpossible in a DAG
Dijkstra, arraysingle sourcen/a
Dijkstra, binary heapsingle source lazyn/a
Dijkstra, Fibonacci heapsingle sourcen/a
Bellman-Fordanysingle sourcedetects (reachable)
SPFAanysingle source worst, often near detects with counters
Floyd-Warshallanyall pairsdetects (diagonal)
Johnsonanyall pairs outputdetects
A* (consistent )single pair Dijkstra's expansionsn/a
Yenk simple pathsn/a

Correctness

Dijkstra: settled distances are exact

Claim. With non-negative weights, whenever a non-stale entry is popped, .

Proof (cut argument). Suppose not, and let be the first vertex popped (non-stale) with . Then (since ) and is reachable (otherwise and the inequality is impossible). Take a true shortest path from to . At the moment is popped, the settled set contains but not , so crosses the cut : let be the first vertex on outside , and its predecessor on .

  • was settled before , so by minimality of , when was settled, and at that moment the edge was relaxed. Hence , the last equality by optimal substructure ('s prefix to is shortest). With the upper-bound property, , and an entry is in the heap.
  • All weights are non-negative, so the part of from to has weight : .

Putting it together: . So the heap held an entry with key smaller than when was popped — impossible for a min-heap — unless , which would give , contradicting the assumption.

The proof uses non-negativity in exactly one place: "the rest of from to cannot have negative weight". The counterexample above is precisely a path whose remainder () is negative. This "greedy stays ahead" structure — the greedy choice is never beaten by any path that leaves the explored region — is the same one behind Prim's algorithm and many greedy proofs in Greedy Algorithms.

Corollary: settled vertices come out in non-decreasing order of distance, which is why Dijkstra can stop as soon as the target is popped, and why "the -th pop of is the -th shortest walk" works for k-shortest walks.

Bellman-Ford: rounds suffice

Claim. After round , the weight of the cheapest walk from to that uses at most edges.

Proof. Induction on . Round 0: only is reachable with 0 edges, and . Step: let be the cheapest walk to with at most edges, and suppose its last edge is (if has 0 edges, and we are done). The prefix to has at most edges, so after round , , and values only decrease. During round the edge is relaxed, so .

If no negative cycle is reachable from , every vertex has a shortest path that is simple, hence has at most edges; after round , , and with the upper-bound property, .

Detection is complete. Suppose a negative cycle is reachable from and, after round , no edge can be relaxed. Then for every , and all these values are finite (the cycle is reachable). Summing over the cycle, the terms cancel (each vertex appears once on each side) and we get , contradicting . So some edge on the cycle is still relaxable in round . Conversely, with no reachable negative cycle, distances are final after round and nothing relaxes. So "round relaxes something" "a negative cycle is reachable from ".

Floyd-Warshall: the DP is right, and in-place updates are safe

Claim. After the outer iteration for , , the shortest path with all intermediate vertices in (assuming no negative cycles).

Proof. Induction on . Consider the shortest path with intermediates in . If avoids as an intermediate, its weight is . Otherwise visits exactly once (with no negative cycles, a shortest path can be taken simple) and splits into and , each with intermediates in and each optimal for that restricted problem, with weights and . So the recurrence takes the minimum of exactly the two possible cases.

In-place updating is safe because during iteration , row and column do not change: and without negative cycles. So it does not matter whether a read sees the old or the new value.

With a negative cycle through , becomes negative during iteration or later, and that is what the diagonal check detects. (Values on and near negative cycles can then decrease very fast — exponentially in in the worst case — which matters for overflow; see Pitfalls.)

Johnson: reweighting preserves shortest paths

Claim. For any potential and : (a) a path is a shortest path under iff it is one under ; (b) has a negative cycle iff does; (c) with from the virtual source, .

Proof. (a) For , . All paths shift by the same constant , so their order is unchanged. (b) For a cycle, and the shift is 0. (c) The triangle inequality for shortest distances from gives , i.e. . All are finite because has an edge to every vertex, and they exist because Bellman-Ford found no negative cycle.

A*: consistent heuristics never reopen a vertex

Claim. If is consistent, then when A* pops a vertex for the first time, ; hence no vertex is ever reopened, and when is popped its is optimal.

Proof. Define reduced weights . Consistency, , says exactly . For any path, (the same telescoping as Johnson's, with as the potential). So the tentative distance A* tracks, , corresponds to the Dijkstra tentative distance under , and A*'s key is Dijkstra's key under plus a constant. A* therefore pops vertices in exactly the order Dijkstra would on the non-negative graph , and Dijkstra's correctness theorem says each popped vertex has its exact distance under , hence (by the path-shift identity) under . Exact distances are never improved later, so no vertex needs reopening.

Two corollaries. First, the values of popped vertices are non-decreasing (they are Dijkstra's popped keys plus a constant). Second, A* with a consistent expands no vertex with , while plain Dijkstra expands every vertex with . Because , the set is contained in , so up to tie-breaking among vertices at exactly the threshold, A* never expands more than Dijkstra. If is admissible but not consistent, A* can pop a vertex with a suboptimal ; it is still optimal if it reopens vertices when improves, but the "each vertex once" guarantee is gone.

Complexity

AlgorithmTimeSpaceNotes
Dijkstra, binary heap, lazyAt most pushes
Dijkstra, binary heap, decrease-keyNeeds an indexed heap
Dijkstra, Fibonacci heapLarge constants
Dijkstra, arrayBest for
Bellman-Ford worst; best (one round + check)Early exit helps on easy inputs only
SPFA worstAverage far better; adversarial inputs exist
Floyd-Warshall alwaysTiny constant, sequential memory access
Johnson for the outputOne Bellman-Ford + Dijkstras
A* worst; often far lessExponential in depth for implicit graphs with bad
0-1 BFS / BFS
Dial (weights ) buckets, or circular
Yen ( simple paths)

Constants and cache behaviour: Floyd-Warshall's inner loop scans rows and sequentially, which compilers vectorize; it often beats heap-based Dijkstra runs up to a few hundred vertices even on sparse graphs. Dijkstra on a real road graph is dominated by cache misses when relaxing neighbours (vertices adjacent in the graph are scattered in memory), which is why road-routing engines reorder vertices for locality.

On the theory side, Duan, Mao, Mao, Shu and Yin (STOC 2025) beat Dijkstra's for directed graphs with a deterministic algorithm, and Bernstein, Nanongkai and Wulff-Nilsen (FOCS 2022) solved negative integer weights in near-linear time. Neither has displaced Dijkstra or Bellman-Ford in practice.

Implementation

Dijkstra with lazy deletion and path reconstruction

Vertices 0..n-1, directed edges (u, v, w) with w >= 0. Tests use the running example with S, A, B, C, D, T = 0..5 plus an isolated vertex 6, and a chain of five edges of weight to make sure distances are 64-bit (the total, , overflows a 32-bit int).

import heapq

INF = float("inf")


def dijkstra(n: int, edges: list[tuple[int, int, int]], s: int) -> tuple[list[float], list[int]]:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        if w < 0:
            raise ValueError("Dijkstra needs non-negative weights")
        adj[u].append((v, w))
    dist = [INF] * n
    parent = [-1] * n
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                      # stale entry
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent


def path_to(parent: list[int], dist: list[float], s: int, t: int) -> list[int]:
    if dist[t] == INF:
        return []
    path = [t]
    while path[-1] != s:
        path.append(parent[path[-1]])
    return path[::-1]


S, A, B, C, D, T = range(6)
EDGES = [(S, A, 4), (S, B, 1), (B, A, 2), (A, C, 1), (B, C, 5), (A, D, 6), (C, D, 3), (C, T, 6), (D, T, 2)]
dist, parent = dijkstra(7, EDGES, S)
assert dist[:6] == [0, 3, 1, 4, 7, 9] and dist[6] == INF
assert path_to(parent, dist, S, T) == [S, B, A, C, D, T]
assert path_to(parent, dist, S, 6) == []
big, _ = dijkstra(6, [(i, i + 1, 10**9) for i in range(5)], 0)
assert big[5] == 5 * 10**9
print("dijkstra ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
    static final long INF = Long.MAX_VALUE;

    /** Returns {dist, parent}; dist[v] == INF if unreachable. */
    static Object[] dijkstra(int n, long[][] edges, int s) {
        List<List<long[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (long[] e : edges) {
            if (e[2] < 0) throw new IllegalArgumentException("negative weight");
            adj.get((int) e[0]).add(new long[]{e[1], e[2]});
        }
        long[] dist = new long[n];
        int[] parent = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);
        dist[s] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.add(new long[]{0, s});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;                 // stale entry
            for (long[] e : adj.get(u)) {
                int v = (int) e[0];
                long nd = d + e[1];
                if (nd < dist[v]) {
                    dist[v] = nd;
                    parent[v] = u;
                    pq.add(new long[]{nd, v});
                }
            }
        }
        return new Object[]{dist, parent};
    }

    static List<Integer> pathTo(int[] parent, long[] dist, int s, int t) {
        List<Integer> path = new ArrayList<>();
        if (dist[t] == INF) return path;
        for (int v = t; v != s; v = parent[v]) path.add(v);
        path.add(s);
        Collections.reverse(path);
        return path;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        long[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {1, 4, 6}, {3, 4, 3}, {3, 5, 6}, {4, 5, 2}};
        Object[] r = dijkstra(7, edges, 0);
        long[] dist = (long[]) r[0];
        int[] parent = (int[]) r[1];
        check(Arrays.equals(Arrays.copyOf(dist, 6), new long[]{0, 3, 1, 4, 7, 9}) && dist[6] == INF, "dist");
        check(pathTo(parent, dist, 0, 5).equals(List.of(0, 2, 1, 3, 4, 5)), "path");
        check(pathTo(parent, dist, 0, 6).isEmpty(), "unreachable");
        long[][] chain = new long[5][];
        for (int i = 0; i < 5; i++) chain[i] = new long[]{i, i + 1, 1_000_000_000L};
        check(((long[]) dijkstra(6, chain, 0)[0])[5] == 5_000_000_000L, "64-bit");
        System.out.println("dijkstra ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>

using i64 = std::int64_t;
constexpr i64 INF = std::numeric_limits<i64>::max();
struct Edge { int u, v; i64 w; };

std::pair<std::vector<i64>, std::vector<int>> dijkstra(int n, const std::vector<Edge>& edges, int s) {
    std::vector<std::vector<std::pair<int, i64>>> adj(n);
    for (const auto& e : edges) {
        if (e.w < 0) throw std::invalid_argument("negative weight");
        adj[e.u].push_back({e.v, e.w});
    }
    std::vector<i64> dist(n, INF);
    std::vector<int> parent(n, -1);
    using Item = std::pair<i64, int>;
    std::priority_queue<Item, std::vector<Item>, std::greater<>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;                    // stale entry
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    return {dist, parent};
}

std::vector<int> path_to(const std::vector<int>& parent, const std::vector<i64>& dist, int s, int t) {
    if (dist[t] == INF) return {};
    std::vector<int> path;
    for (int v = t; v != s; v = parent[v]) path.push_back(v);
    path.push_back(s);
    std::reverse(path.begin(), path.end());
    return path;
}

int main() {
    std::vector<Edge> edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {1, 4, 6}, {3, 4, 3}, {3, 5, 6}, {4, 5, 2}};
    auto [dist, parent] = dijkstra(7, edges, 0);
    assert((std::vector<i64>(dist.begin(), dist.begin() + 6) == std::vector<i64>{0, 3, 1, 4, 7, 9}) && dist[6] == INF);
    assert((path_to(parent, dist, 0, 5) == std::vector<int>{0, 2, 1, 3, 4, 5}));
    assert(path_to(parent, dist, 0, 6).empty());
    std::vector<Edge> chain;
    for (int i = 0; i < 5; ++i) chain.push_back({i, i + 1, 1'000'000'000});
    assert(dijkstra(6, chain, 0).first[5] == 5'000'000'000LL);
    std::cout << "dijkstra ok\n";
}
type WEdge = [number, number, number];

class MinHeap {
  private a: [number, number][] = [];
  get size(): number { return this.a.length; }
  push(x: [number, number]): void {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop(): [number, number] {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

function dijkstra(n: number, edges: WEdge[], s: number): [number[], number[]] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    if (w < 0) throw new Error("negative weight");
    adj[u].push([v, w]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  const parent = new Array<number>(n).fill(-1);
  dist[s] = 0;
  const pq = new MinHeap();
  pq.push([0, s]);
  while (pq.size > 0) {
    const [d, u] = pq.pop();
    if (d > dist[u]) continue;                       // stale entry
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        parent[v] = u;
        pq.push([dist[v], v]);
      }
    }
  }
  return [dist, parent];
}

function pathTo(parent: number[], dist: number[], s: number, t: number): number[] {
  if (dist[t] === Infinity) return [];
  const path = [t];
  while (path[path.length - 1] !== s) path.push(parent[path[path.length - 1]]);
  return path.reverse();
}

function check(ok: boolean, what: string): void { if (!ok) throw new Error(what); }

const edges: WEdge[] = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [1, 4, 6], [3, 4, 3], [3, 5, 6], [4, 5, 2]];
const [dist, parent] = dijkstra(7, edges, 0);
check(dist.slice(0, 6).join(",") === "0,3,1,4,7,9" && dist[6] === Infinity, "dist");
check(pathTo(parent, dist, 0, 5).join(",") === "0,2,1,3,4,5", "path");
check(pathTo(parent, dist, 0, 6).length === 0, "unreachable");
const chain: WEdge[] = Array.from({ length: 5 }, (_, i) => [i, i + 1, 1e9] as WEdge);
check(dijkstra(6, chain, 0)[0][5] === 5e9, "large");             // exact: below 2^53
console.log("dijkstra ok");

Bellman-Ford with negative-cycle recovery

Returns the distances and, if a negative cycle is reachable from s, one such cycle as a vertex list in edge order (empty otherwise). Tests: the trace example (S, A, B, C, D, E = 0..5, edges in the same bad order), the same graph plus E→B -1, and a negative cycle on two extra vertices that s cannot reach (it must not be reported).

INF = float("inf")


def bellman_ford(n: int, edges: list[tuple[int, int, int]], s: int) -> tuple[list[float], list[int]]:
    dist = [INF] * n
    parent = [-1] * n
    dist[s] = 0
    x = -1
    for _ in range(n):                    # rounds 1..n-1 relax; round n detects
        x = -1
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                x = v
        if x == -1:
            return dist, []               # converged: no reachable negative cycle
    for _ in range(n):                    # walk back n steps to land on the cycle
        x = parent[x]
    cycle = [x]
    v = parent[x]
    while v != x:
        cycle.append(v)
        v = parent[v]
    cycle.reverse()
    return dist, cycle


def is_negative_cycle(cycle: list[int], edges: list[tuple[int, int, int]]) -> bool:
    best = {}
    for u, v, w in edges:
        best[(u, v)] = min(w, best.get((u, v), INF))
    pairs = list(zip(cycle, cycle[1:] + cycle[:1]))
    return bool(cycle) and all(p in best for p in pairs) and sum(best[p] for p in pairs) < 0


S, A, B, C, D, E = range(6)
EDGES = [(D, E, 1), (C, E, 5), (C, D, -1), (B, D, 6), (A, C, 2), (B, A, -3), (S, B, 5), (S, A, 4)]
dist, cyc = bellman_ford(6, EDGES, S)
assert dist == [0, 2, 5, 4, 3, 4] and cyc == []

neg = EDGES + [(E, B, -1)]                # B -> A -> C -> D -> E -> B has weight -2
_, cyc = bellman_ford(6, neg, S)
assert sorted(cyc) == [A, B, C, D, E] and is_negative_cycle(cyc, neg)

far = EDGES + [(6, 7, -1), (7, 6, -1)]    # negative cycle not reachable from S
dist, cyc = bellman_ford(8, far, S)
assert cyc == [] and dist[6] == INF
print("bellman-ford ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BellmanFord {
    static final long INF = Long.MAX_VALUE;

    /** Fills dist; returns a reachable negative cycle in edge order, or an empty list. */
    static List<Integer> bellmanFord(int n, long[][] edges, int s, long[] dist) {
        int[] parent = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);
        dist[s] = 0;
        int x = -1;
        for (int round = 0; round < n; round++) {
            x = -1;
            for (long[] e : edges) {
                int u = (int) e[0], v = (int) e[1];
                if (dist[u] != INF && dist[u] + e[2] < dist[v]) {
                    dist[v] = dist[u] + e[2];
                    parent[v] = u;
                    x = v;
                }
            }
            if (x == -1) return new ArrayList<>();
        }
        for (int i = 0; i < n; i++) x = parent[x];
        List<Integer> cycle = new ArrayList<>();
        cycle.add(x);
        for (int v = parent[x]; v != x; v = parent[v]) cycle.add(v);
        Collections.reverse(cycle);
        return cycle;
    }

    static boolean isNegativeCycle(List<Integer> c, long[][] edges) {
        Map<Long, Long> best = new HashMap<>();
        for (long[] e : edges) best.merge(e[0] * 1_000_003L + e[1], e[2], Math::min);
        if (c.isEmpty()) return false;
        long sum = 0;
        for (int i = 0; i < c.size(); i++) {
            Long w = best.get((long) c.get(i) * 1_000_003L + c.get((i + 1) % c.size()));
            if (w == null) return false;
            sum += w;
        }
        return sum < 0;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        long[][] edges = {{4, 5, 1}, {3, 5, 5}, {3, 4, -1}, {2, 4, 6}, {1, 3, 2}, {2, 1, -3}, {0, 2, 5}, {0, 1, 4}};
        long[] dist = new long[6];
        check(bellmanFord(6, edges, 0, dist).isEmpty(), "no cycle");
        check(Arrays.equals(dist, new long[]{0, 2, 5, 4, 3, 4}), "dist");

        long[][] neg = Arrays.copyOf(edges, edges.length + 1);
        neg[edges.length] = new long[]{5, 2, -1};
        List<Integer> cyc = bellmanFord(6, neg, 0, new long[6]);
        List<Integer> sorted = new ArrayList<>(cyc);
        Collections.sort(sorted);
        check(sorted.equals(List.of(1, 2, 3, 4, 5)) && isNegativeCycle(cyc, neg), "cycle");

        long[][] far = Arrays.copyOf(edges, edges.length + 2);
        far[edges.length] = new long[]{6, 7, -1};
        far[edges.length + 1] = new long[]{7, 6, -1};
        long[] d8 = new long[8];
        check(bellmanFord(8, far, 0, d8).isEmpty() && d8[6] == INF, "unreachable cycle");
        System.out.println("bellman-ford ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <utility>
#include <vector>

using i64 = std::int64_t;
constexpr i64 INF = std::numeric_limits<i64>::max();
struct Edge { int u, v; i64 w; };

// Fills dist; returns a reachable negative cycle in edge order, or an empty vector.
std::vector<int> bellman_ford(int n, const std::vector<Edge>& edges, int s, std::vector<i64>& dist) {
    dist.assign(n, INF);
    std::vector<int> parent(n, -1);
    dist[s] = 0;
    int x = -1;
    for (int round = 0; round < n; ++round) {
        x = -1;
        for (const auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                parent[e.v] = e.u;
                x = e.v;
            }
        }
        if (x == -1) return {};
    }
    for (int i = 0; i < n; ++i) x = parent[x];
    std::vector<int> cycle{x};
    for (int v = parent[x]; v != x; v = parent[v]) cycle.push_back(v);
    std::reverse(cycle.begin(), cycle.end());
    return cycle;
}

bool is_negative_cycle(const std::vector<int>& c, const std::vector<Edge>& edges) {
    std::map<std::pair<int, int>, i64> best;
    for (const auto& e : edges) {
        auto it = best.find({e.u, e.v});
        if (it == best.end() || e.w < it->second) best[{e.u, e.v}] = e.w;
    }
    if (c.empty()) return false;
    i64 sum = 0;
    for (std::size_t i = 0; i < c.size(); ++i) {
        auto it = best.find({c[i], c[(i + 1) % c.size()]});
        if (it == best.end()) return false;
        sum += it->second;
    }
    return sum < 0;
}

int main() {
    std::vector<Edge> edges = {{4, 5, 1}, {3, 5, 5}, {3, 4, -1}, {2, 4, 6}, {1, 3, 2}, {2, 1, -3}, {0, 2, 5}, {0, 1, 4}};
    std::vector<i64> dist;
    assert(bellman_ford(6, edges, 0, dist).empty());
    assert((dist == std::vector<i64>{0, 2, 5, 4, 3, 4}));

    auto neg = edges;
    neg.push_back({5, 2, -1});
    auto cyc = bellman_ford(6, neg, 0, dist);
    auto sorted = cyc;
    std::sort(sorted.begin(), sorted.end());
    assert((sorted == std::vector<int>{1, 2, 3, 4, 5}) && is_negative_cycle(cyc, neg));

    auto far = edges;
    far.push_back({6, 7, -1});
    far.push_back({7, 6, -1});
    assert(bellman_ford(8, far, 0, dist).empty() && dist[6] == INF);
    std::cout << "bellman-ford ok\n";
}
type WEdge = [number, number, number];

// Returns [dist, cycle]; cycle is a reachable negative cycle in edge order, or [].
function bellmanFord(n: number, edges: WEdge[], s: number): [number[], number[]] {
  const dist = new Array<number>(n).fill(Infinity);
  const parent = new Array<number>(n).fill(-1);
  dist[s] = 0;
  let x = -1;
  for (let round = 0; round < n; round++) {
    x = -1;
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        x = v;
      }
    }
    if (x === -1) return [dist, []];
  }
  for (let i = 0; i < n; i++) x = parent[x];
  const cycle = [x];
  for (let v = parent[x]; v !== x; v = parent[v]) cycle.push(v);
  return [dist, cycle.reverse()];
}

function isNegativeCycle(c: number[], edges: WEdge[]): boolean {
  const best = new Map<string, number>();
  for (const [u, v, w] of edges) best.set(`${u},${v}`, Math.min(w, best.get(`${u},${v}`) ?? Infinity));
  if (c.length === 0) return false;
  let sum = 0;
  for (let i = 0; i < c.length; i++) {
    const w = best.get(`${c[i]},${c[(i + 1) % c.length]}`);
    if (w === undefined) return false;
    sum += w;
  }
  return sum < 0;
}

function check(ok: boolean, what: string): void { if (!ok) throw new Error(what); }

const edges: WEdge[] = [[4, 5, 1], [3, 5, 5], [3, 4, -1], [2, 4, 6], [1, 3, 2], [2, 1, -3], [0, 2, 5], [0, 1, 4]];
const [dist, none] = bellmanFord(6, edges, 0);
check(dist.join(",") === "0,2,5,4,3,4" && none.length === 0, "dist");
const neg: WEdge[] = [...edges, [5, 2, -1]];
const [, cyc] = bellmanFord(6, neg, 0);
check([...cyc].sort((a, b) => a - b).join(",") === "1,2,3,4,5" && isNegativeCycle(cyc, neg), "cycle");
const far: WEdge[] = [...edges, [6, 7, -1], [7, 6, -1]];
const [d8, c8] = bellmanFord(8, far, 0);
check(c8.length === 0 && d8[6] === Infinity, "unreachable cycle");
console.log("bellman-ford ok");

Floyd-Warshall with path reconstruction and negative-cycle check

nxt[i][j] is the vertex after i on a shortest i → j path. Tests use the four-vertex example, an extra isolated vertex 4, and the same graph plus 3→1 -5 for the negative cycle.

INF = float("inf")


def floyd_warshall(n: int, edges: list[tuple[int, int, int]]) -> tuple[list[list[float]], list[list[int]]]:
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else -1 for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        if w < d[u][v]:                   # keep the lightest parallel edge
            d[u][v] = w
            nxt[u][v] = v
    for k in range(n):
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            di, ni = d[i], nxt[i]
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
                    ni[j] = ni[k]
    return d, nxt


def fw_path(nxt: list[list[int]], i: int, j: int) -> list[int]:
    if nxt[i][j] == -1:
        return []
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path


def has_negative_cycle(d: list[list[float]]) -> bool:
    return any(d[i][i] < 0 for i in range(len(d)))


E4 = [(0, 1, 3), (0, 2, 8), (1, 2, -2), (1, 3, 1), (2, 3, 2), (3, 0, 2)]
d, nxt = floyd_warshall(5, E4)
assert [row[:4] for row in d[:4]] == [[0, 3, 1, 3], [2, 0, -2, 0], [4, 7, 0, 2], [2, 5, 3, 0]]
assert fw_path(nxt, 0, 3) == [0, 1, 2, 3] and fw_path(nxt, 2, 1) == [2, 3, 0, 1]
assert d[0][4] == INF and fw_path(nxt, 0, 4) == [] and not has_negative_cycle(d)
d2, _ = floyd_warshall(4, E4 + [(3, 1, -5)])
assert has_negative_cycle(d2)
print("floyd-warshall ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FloydWarshall {
    static final long INF = Long.MAX_VALUE / 4;     // headroom: INF + small negative stays "infinite"

    static long[][] d;
    static int[][] nxt;

    static void run(int n, long[][] edges) {
        d = new long[n][n];
        nxt = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(d[i], INF);
            Arrays.fill(nxt[i], -1);
            d[i][i] = 0;
            nxt[i][i] = i;
        }
        for (long[] e : edges) {
            int u = (int) e[0], v = (int) e[1];
            if (e[2] < d[u][v]) { d[u][v] = e[2]; nxt[u][v] = v; }
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++) {
                if (d[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (d[k][j] == INF) continue;
                    long cand = d[i][k] + d[k][j];
                    if (cand < d[i][j]) { d[i][j] = cand; nxt[i][j] = nxt[i][k]; }
                }
            }
    }

    static List<Integer> path(int i, int j) {
        List<Integer> p = new ArrayList<>();
        if (nxt[i][j] == -1) return p;
        p.add(i);
        while (i != j) { i = nxt[i][j]; p.add(i); }
        return p;
    }

    static boolean hasNegativeCycle() {
        for (int i = 0; i < d.length; i++) if (d[i][i] < 0) return true;
        return false;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        long[][] e4 = {{0, 1, 3}, {0, 2, 8}, {1, 2, -2}, {1, 3, 1}, {2, 3, 2}, {3, 0, 2}};
        run(5, e4);
        long[][] want = {{0, 3, 1, 3}, {2, 0, -2, 0}, {4, 7, 0, 2}, {2, 5, 3, 0}};
        for (int i = 0; i < 4; i++) check(Arrays.equals(Arrays.copyOf(d[i], 4), want[i]), "row " + i);
        check(path(0, 3).equals(List.of(0, 1, 2, 3)) && path(2, 1).equals(List.of(2, 3, 0, 1)), "paths");
        check(d[0][4] == INF && path(0, 4).isEmpty() && !hasNegativeCycle(), "unreachable");
        long[][] neg = Arrays.copyOf(e4, e4.length + 1);
        neg[e4.length] = new long[]{3, 1, -5};
        run(4, neg);
        check(hasNegativeCycle(), "negative cycle");
        System.out.println("floyd-warshall ok");
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using i64 = std::int64_t;
constexpr i64 INF = std::numeric_limits<i64>::max() / 4;
struct Edge { int u, v; i64 w; };

struct FloydWarshall {
    std::vector<std::vector<i64>> d;
    std::vector<std::vector<int>> nxt;

    FloydWarshall(int n, const std::vector<Edge>& edges)
        : d(n, std::vector<i64>(n, INF)), nxt(n, std::vector<int>(n, -1)) {
        for (int i = 0; i < n; ++i) { d[i][i] = 0; nxt[i][i] = i; }
        for (const auto& e : edges)
            if (e.w < d[e.u][e.v]) { d[e.u][e.v] = e.w; nxt[e.u][e.v] = e.v; }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i) {
                if (d[i][k] == INF) continue;
                for (int j = 0; j < n; ++j) {
                    if (d[k][j] == INF) continue;
                    if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; nxt[i][j] = nxt[i][k]; }
                }
            }
    }

    std::vector<int> path(int i, int j) const {
        if (nxt[i][j] == -1) return {};
        std::vector<int> p{i};
        while (i != j) { i = nxt[i][j]; p.push_back(i); }
        return p;
    }

    bool has_negative_cycle() const {
        for (std::size_t i = 0; i < d.size(); ++i) if (d[i][i] < 0) return true;
        return false;
    }
};

int main() {
    std::vector<Edge> e4 = {{0, 1, 3}, {0, 2, 8}, {1, 2, -2}, {1, 3, 1}, {2, 3, 2}, {3, 0, 2}};
    FloydWarshall fw(5, e4);
    std::vector<std::vector<i64>> want = {{0, 3, 1, 3}, {2, 0, -2, 0}, {4, 7, 0, 2}, {2, 5, 3, 0}};
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j) assert(fw.d[i][j] == want[i][j]);
    assert((fw.path(0, 3) == std::vector<int>{0, 1, 2, 3}) && (fw.path(2, 1) == std::vector<int>{2, 3, 0, 1}));
    assert(fw.d[0][4] == INF && fw.path(0, 4).empty() && !fw.has_negative_cycle());
    auto neg = e4;
    neg.push_back({3, 1, -5});
    assert(FloydWarshall(4, neg).has_negative_cycle());
    std::cout << "floyd-warshall ok\n";
}
type WEdge = [number, number, number];

function floydWarshall(n: number, edges: WEdge[]): [number[][], number[][]] {
  const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  const nxt = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? j : -1)));
  for (const [u, v, w] of edges) if (w < d[u][v]) { d[u][v] = w; nxt[u][v] = v; }
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++) {
      if (d[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; nxt[i][j] = nxt[i][k]; }
    }
  return [d, nxt];
}

function fwPath(nxt: number[][], i: number, j: number): number[] {
  if (nxt[i][j] === -1) return [];
  const p = [i];
  while (i !== j) { i = nxt[i][j]; p.push(i); }
  return p;
}

const hasNegativeCycle = (d: number[][]) => d.some((row, i) => row[i] < 0);
function check(ok: boolean, what: string): void { if (!ok) throw new Error(what); }

const e4: WEdge[] = [[0, 1, 3], [0, 2, 8], [1, 2, -2], [1, 3, 1], [2, 3, 2], [3, 0, 2]];
const [d, nxt] = floydWarshall(5, e4);
check(JSON.stringify(d.slice(0, 4).map((r) => r.slice(0, 4))) === "[[0,3,1,3],[2,0,-2,0],[4,7,0,2],[2,5,3,0]]", "matrix");
check(fwPath(nxt, 0, 3).join(",") === "0,1,2,3" && fwPath(nxt, 2, 1).join(",") === "2,3,0,1", "paths");
check(d[0][4] === Infinity && fwPath(nxt, 0, 4).length === 0 && !hasNegativeCycle(d), "unreachable");
check(hasNegativeCycle(floydWarshall(4, [...e4, [3, 1, -5]])[0]), "negative cycle");
console.log("floyd-warshall ok");

Variant: Dijkstra for dense graphs

INF = float("inf")


def dijkstra_dense(w: list[list[float]], s: int) -> list[float]:
    """w[u][v] = edge weight or INF. O(V^2): no heap, a linear scan per round."""
    n = len(w)
    dist = [INF] * n
    done = [False] * n
    dist[s] = 0
    for _ in range(n):
        u, best = -1, INF
        for v in range(n):
            if not done[v] and dist[v] < best:
                u, best = v, dist[v]
        if u == -1:
            break                         # the rest is unreachable
        done[u] = True
        row = w[u]
        for v in range(n):
            if best + row[v] < dist[v]:
                dist[v] = best + row[v]
    return dist


M = [[INF] * 6 for _ in range(6)]
for u, v, c in [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (1, 4, 6), (3, 4, 3), (3, 5, 6), (4, 5, 2)]:
    M[u][v] = c
assert dijkstra_dense(M, 0) == [0, 3, 1, 4, 7, 9]
print("dense dijkstra ok")

Variant: Johnson's algorithm

import heapq
import random

INF = float("inf")


def johnson(n: int, edges: list[tuple[int, int, int]]) -> list[list[float]] | None:
    """All-pairs shortest paths; None if there is a negative cycle."""
    h = [0] * n                           # Bellman-Ford from a virtual source q (dist 0 to everyone)
    for _ in range(n):
        changed = False
        for u, v, w in edges:
            if h[u] + w < h[v]:
                h[v] = h[u] + w
                changed = True
        if not changed:
            break
    else:
        return None                       # still changing after n rounds: negative cycle
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w + h[u] - h[v]))   # reweighted, guaranteed >= 0
    out = []
    for s in range(n):
        dist = [INF] * n
        dist[s] = 0
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(pq, (d + w, v))
        out.append([dist[v] - h[s] + h[v] if dist[v] < INF else INF for v in range(n)])
    return out


def floyd(n, edges):
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


E4 = [(0, 1, 3), (0, 2, 8), (1, 2, -2), (1, 3, 1), (2, 3, 2), (3, 0, 2)]
assert johnson(4, E4) == [[0, 3, 1, 3], [2, 0, -2, 0], [4, 7, 0, 2], [2, 5, 3, 0]]
assert johnson(4, E4 + [(3, 1, -5)]) is None
rng = random.Random(7)
checked = 0
for _ in range(300):                      # random graphs with negative edges, compared against Floyd-Warshall
    n = rng.randint(1, 8)
    es = [(u, v, rng.randint(-5, 10)) for u in range(n) for v in range(u + 1, n) if rng.random() < 0.5]
    es += [(v, u, rng.randint(0, 20)) for u, v, _ in es if rng.random() < 0.3]   # back edges create cycles
    ref = floyd(n, es)
    if any(ref[i][i] < 0 for i in range(n)):
        assert johnson(n, es) is None
    else:
        assert johnson(n, es) == ref
        checked += 1
assert checked > 100
print("johnson ok")

Variant: A* on a grid, reproducing the measurement table

import heapq
import math
import random

INF = float("inf")
SQ2 = math.sqrt(2)


def make_grid(rows: int, cols: int, wall_p: float, seed: int) -> list[list[str]]:
    rnd = random.Random(seed)
    g = [["#" if rnd.random() < wall_p else "." for _ in range(cols)] for _ in range(rows)]
    g[0][0] = g[rows - 1][cols - 1] = "."
    return g


def astar(g, start, goal, h, diagonal: bool) -> tuple[float | None, int]:
    """Returns (path cost, vertices expanded). Ties on f are broken towards larger g."""
    R, C = len(g), len(g[0])
    moves = [(1, 0, 1), (-1, 0, 1), (0, 1, 1), (0, -1, 1)]
    if diagonal:
        moves += [(1, 1, SQ2), (1, -1, SQ2), (-1, 1, SQ2), (-1, -1, SQ2)]
    dist = {start: 0.0}
    pq = [(h(start), 0.0, start)]
    closed = set()
    while pq:
        _, _, u = heapq.heappop(pq)
        if u in closed:
            continue                      # consistent h: a vertex is never reopened
        closed.add(u)
        if u == goal:
            return dist[u], len(closed)
        for dr, dc, w in moves:
            r, c = u[0] + dr, u[1] + dc
            if not (0 <= r < R and 0 <= c < C) or g[r][c] == "#":
                continue
            if diagonal and dr and dc and (g[u[0] + dr][u[1]] == "#" or g[u[0]][u[1] + dc] == "#"):
                continue                  # no squeezing between two walls diagonally
            nd = dist[u] + w
            if nd < dist.get((r, c), INF) - 1e-12:
                dist[(r, c)] = nd
                heapq.heappush(pq, (nd + h((r, c)), -nd, (r, c)))
    return None, len(closed)


g = make_grid(101, 101, 0.25, 1)
goal = (100, 100)
zero = lambda p: 0
manhattan = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
euclid = lambda p: math.hypot(p[0] - goal[0], p[1] - goal[1])


def octile(p):
    dx, dy = abs(p[0] - goal[0]), abs(p[1] - goal[1])
    return max(dx, dy) + (SQ2 - 1) * min(dx, dy)


four = [astar(g, (0, 0), goal, h, False) for h in (zero, euclid, manhattan)]
eight = [astar(g, (0, 0), goal, h, True) for h in (zero, euclid, octile)]
assert [c for c, _ in four] == [200, 200, 200] and [n for _, n in four] == [7522, 6509, 924]
assert all(abs(c - 170.953) < 1e-3 for c, _ in eight) and [n for _, n in eight] == [7522, 4944, 4115]
open_grid = [["."] * 101 for _ in range(101)]
assert [astar(open_grid, (0, 0), goal, h, False)[1] for h in (zero, manhattan)] == [10201, 201]
print("a-star ok")

Variant: at most k edges, layered Dijkstra, and Yen's k shortest simple paths

import heapq

INF = float("inf")


def cheapest_with_k_edges(n: int, edges: list[tuple[int, int, int]], s: int, t: int, k: int) -> float:
    """Bellman-Ford limited to k rounds; relax from a snapshot so each round adds at most one edge."""
    dist = [INF] * n
    dist[s] = 0
    for _ in range(k):
        prev = dist[:]
        for u, v, w in edges:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return dist[t]


def dijkstra_one_discount(n: int, edges: list[tuple[int, int, int]], s: int, t: int) -> int:
    """Layered graph: state (v, used), one edge may be taken at half price (floor)."""
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [[INF, INF] for _ in range(n)]
    dist[s][0] = 0
    pq = [(0, s, 0)]
    while pq:
        d, u, used = heapq.heappop(pq)
        if d > dist[u][used]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v][used]:
                dist[v][used] = d + w
                heapq.heappush(pq, (d + w, v, used))
            if not used and d + w // 2 < dist[v][1]:
                dist[v][1] = d + w // 2
                heapq.heappush(pq, (d + w // 2, v, 1))
    return min(dist[t])


def shortest(adj, s, t, banned_v, banned_e):
    dist, par = {s: 0}, {s: None}
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == t:
            path = [t]
            while par[path[-1]] is not None:
                path.append(par[path[-1]])
            return d, path[::-1]
        for v, w in adj[u]:
            if v in banned_v or (u, v) in banned_e:
                continue
            if d + w < dist.get(v, INF):
                dist[v], par[v] = d + w, u
                heapq.heappush(pq, (d + w, v))
    return None


def yen(n: int, edges: list[tuple[int, int, int]], s: int, t: int, k: int) -> list[tuple[int, list[int]]]:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    wt = {}
    for u, v, w in edges:
        adj[u].append((v, w))
        wt[(u, v)] = w
    first = shortest(adj, s, t, set(), set())
    if first is None:
        return []
    found, candidates = [first], []
    while len(found) < k:
        last = found[-1][1]
        for i in range(len(last) - 1):
            spur, root = last[i], last[: i + 1]
            banned_e = {(p[i], p[i + 1]) for _, p in found if p[: i + 1] == root and len(p) > i + 1}
            banned_v = set(root[:-1])
            r = shortest(adj, spur, t, banned_v, banned_e)
            if r is not None:
                cost = sum(wt[(root[j], root[j + 1])] for j in range(i)) + r[0]
                cand = (cost, root[:-1] + r[1])
                if cand not in candidates and cand not in found:
                    heapq.heappush(candidates, cand)
        if not candidates:
            break
        found.append(heapq.heappop(candidates))
    return found


S, A, B, C, D, T = range(6)
EDGES = [(S, A, 4), (S, B, 1), (B, A, 2), (A, C, 1), (B, C, 5), (A, D, 6), (C, D, 3), (C, T, 6), (D, T, 2)]
assert cheapest_with_k_edges(6, EDGES, S, T, 5) == 9      # S B A C D T uses 5 edges
assert cheapest_with_k_edges(6, EDGES, S, T, 4) == 10     # S A C D T or S B A C T
assert cheapest_with_k_edges(6, EDGES, S, T, 3) == 11     # S A C T, S B C T is 12
assert cheapest_with_k_edges(6, EDGES, S, T, 2) == INF
assert dijkstra_one_discount(6, EDGES, S, T) == 7         # S B A C, then C -> T at half price: 4 + 3
print("k-edges and layered ok")
paths = yen(6, EDGES, S, T, 3)
assert [c for c, _ in paths] == [9, 10, 10]
assert paths[0][1] == [S, B, A, C, D, T]
assert {tuple(p) for _, p in paths[1:]} == {(S, A, C, D, T), (S, B, A, C, T)}
print("yen ok")

Variant: SPFA with negative-cycle detection, and the input that defeats it

import random
from collections import deque

INF = float("inf")


def spfa(n: int, edges: list[tuple[int, int, int]], s: int) -> tuple[list[float] | None, int]:
    """Returns (dist or None on a reachable negative cycle, number of queue pops)."""
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [INF] * n
    hops = [0] * n                        # edges on the current best path to v
    inq = [False] * n
    dist[s] = 0
    q = deque([s])
    inq[s] = True
    pops = 0
    while q:
        u = q.popleft()
        inq[u] = False
        pops += 1
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                hops[v] = hops[u] + 1
                if hops[v] >= n:          # a path with n edges repeats a vertex: negative cycle
                    return None, pops
                if not inq[v]:
                    inq[v] = True
                    q.append(v)
    return dist, pops


def crafted(n: int) -> list[tuple[int, int, int]]:
    """Direct edges 0 -> i (bad, added in decreasing i) plus a cheap chain i -> i+1."""
    return [(0, i, n + 2 * i) for i in range(n - 1, 0, -1)] + [(i, i + 1, 1) for i in range(1, n - 1)]


for n, expected in ((100, 4951), (1000, 499501)):
    dist, pops = spfa(n, crafted(n), 0)
    assert pops == expected                       # about n^2 / 2: Bellman-Ford's worst case
    assert dist[n - 1] == (n + 2) + (n - 2)       # 0 -> 1 directly, then the chain
rng = random.Random(1)
rand = [(0, i, rng.randint(1, 100)) for i in range(1, 1000)]
rand += [(rng.randrange(1000), rng.randrange(1000), rng.randint(1, 100)) for _ in range(1000)]
assert spfa(1000, rand, 0)[1] == 1079                 # random graph of the same size: ~1 pop per vertex
assert spfa(3, [(0, 1, 1), (1, 2, -2), (2, 1, 1)], 0)[0] is None
print("spfa ok")

Real-world uses

Link-state routing: OSPF and IS-IS run Dijkstra. Every router floods the state of its own links to the whole area, so every router holds the same graph, and each one runs Dijkstra — called the SPF (shortest path first) calculation in OSPF — with itself as the source to build its routing table. Link costs are configured by operators (by default often derived from interface bandwidth). When a link fails, the flood triggers a new SPF run; routers implement incremental SPF and throttling timers because a flapping link would otherwise force constant recomputation. The Network Layer page works through a link-state example step by step.

Distance-vector routing: RIP runs distributed Bellman-Ford. A RIP router knows only its neighbours' distance vectors. Every 30 seconds it sends its own vector to its neighbours, and each router sets — exactly one Bellman-Ford relaxation per edge, executed asynchronously by different machines. The algorithm's " rounds" becomes a convergence time measured in update intervals, and the lack of a global view causes count-to-infinity: after a failure, two routers can keep increasing their distances via each other one step per round. RIP caps distances at 15 hops (16 means unreachable) to bound that, and adds split horizon and poison reverse. The Network Layer page traces count-to-infinity row by row.

BGP: path-vector, policy over distance. Between autonomous systems, BGP is a descendant of distance-vector that advertises the full AS path instead of a number, which lets routers reject paths containing themselves (no count-to-infinity) and choose routes by business policy rather than by shortest distance. It is not a shortest-path algorithm in the sense of this lesson, and the route it picks can be longer than the shortest one by design. See BGP.

Maps and navigation. Plain Dijkstra on a continental road network (tens of millions of vertices) takes seconds per query, too slow for a service answering many queries per second. Production routers preprocess. Contraction hierarchies (Geisberger, Sanders, Schultes and Delling, "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks", WEA 2008, LNCS 5038) order vertices by "importance", contract them one at a time while adding shortcut edges that preserve shortest-path distances, and answer a query with a bidirectional Dijkstra that only moves "upwards" in the hierarchy. The paper reports query times well under a millisecond on the road network of Western Europe after minutes of preprocessing. The open-source OSRM router implements contraction hierarchies; other systems use related techniques (customizable route planning / multi-level partitions, which handle traffic-dependent weights better, and the ALT landmark heuristic for A*).

Games and robotics. A* on grids, navigation meshes or waypoint graphs is the standard game pathfinder. Weighted A* (, ) returns paths at most times optimal while expanding far fewer nodes; robot planners use incremental variants such as D* Lite that repair the search when the map changes.

Currency arbitrage and negative cycles. With exchange rates , a cycle of trades is profitable iff , iff . Weight each edge and a negative cycle is an arbitrage opportunity; Bellman-Ford finds one.

Constraint solving. A system of difference constraints has a solution iff the constraint graph (edge with weight , plus a virtual source) has no negative cycle, and the shortest distances are a solution (CLRS section 24.4). This is used in scheduling with relative timing constraints and in the theory solvers of SMT solvers for difference logic.

All-pairs on small graphs. Floyd-Warshall is the practical choice for distance tables over a few hundred locations and for transitive closure of small relations; Graph Algorithms in the Real World collects more cases.

Pitfalls & edge cases

  • Using Dijkstra with negative edges. With a settled flag it returns wrong answers; without one it can take exponential time; with a negative cycle it never terminates. If any weight can be negative, use Bellman-Ford or Johnson.
  • Adding a constant to make weights non-negative. Changes which path is shortest (it penalizes edge count). Use potentials.
  • Forgetting the stale-entry check. Without if d > dist[u]: continue, a vertex is re-expanded once per stale entry, which can make the run -ish on dense inputs; the answer is still right with non-negative weights, the time is not.
  • Marking visited when pushing instead of when popping. A vertex's distance is final only when it is popped. Marking it on push freezes the first, possibly non-optimal, distance.
  • Integer overflow. INT_MAX + w wraps negative and "improves" everything. Use 64-bit distances, and either skip relaxations from or use so that cannot overflow. In Floyd-Warshall, skip when either or is : with negative edges, looks smaller than .
  • Overflow in Floyd-Warshall with negative cycles. Distances along negative cycles can decrease exponentially fast during the triple loop. If a negative cycle is possible, clamp at (cp-algorithms recommends checking and clamping) or detect cycles first.
  • Bellman-Ford relaxing from . INF + (-3) < INF is true. Guard with dist[u] != INF, otherwise unreachable vertices get finite garbage, and "negative cycle reachable from " becomes "negative cycle anywhere".
  • k-stops without a snapshot. Relaxing in place lets one round extend a path by several edges, so the "at most k edges" limit is silently violated. Copy dist before each round.
  • Loop order in Floyd-Warshall. k must be the outermost loop. i, j, k order is a common bug that gives wrong answers on some inputs and is hard to catch with small tests.
  • Undirected graphs. Add both directions. And remember that a negative undirected edge is a negative cycle.
  • Self-loops and parallel edges. Keep the minimum parallel edge in matrix-based algorithms; a negative self-loop is a negative cycle; a non-negative self-loop is irrelevant.
  • Unreachable targets. Return or "IMPOSSIBLE", not printed as inf or 9223372036854775807. Do not reconstruct a path from parent[t] = -1.
  • Inadmissible heuristics. Manhattan distance on an 8-neighbour grid, or Euclidean distance scaled by a too-large speed, overestimates, and A* returns suboptimal paths without any error.
  • Floating-point weights. Accumulated rounding with costs can make nd < dist[v] succeed spuriously; compare with a small epsilon, or use integer costs such as 10 and 14 for straight and diagonal moves.

Variations

Decision table

Graph and questionUseTime
Unweighted (all weights equal), single sourceBFS
Weights 0 or 10-1 BFS (deque)
Small integer weights Dial's buckets, or Dijkstra
DAG, any weightsTopological-order DP
Non-negative weights, single source, sparseDijkstra, binary heap
Non-negative weights, single source, dense ()Dijkstra, array
Non-negative, single pair, geometric heuristic availableA* (bidirectional if both ends known) Dijkstra
Many queries on a fixed road networkContraction hierarchies / other preprocessingms per query after preprocessing
Negative weights, single sourceBellman-Ford (SPFA as a heuristic speed-up)
"Is there a negative cycle?"Bellman-Ford round with a virtual source; or Floyd-Warshall diagonal /
All pairs, ~500Floyd-Warshall
All pairs, sparse, non-negativeDijkstra from every vertex
All pairs, sparse, negative edgesJohnson
Reachability for all pairsWarshall with bitsets, or SCC + DAG closure
At most edgesBellman-Ford rounds with snapshot / layered graph
Extra state (coupons, fuel, parity)Dijkstra on the product graph (vertex, state)
shortest walksDijkstra popping each vertex up to times; Eppstein
shortest simple pathsYen
Minimize the maximum edge (bottleneck)Dijkstra with max, or MST path
Maximize product of probabilities Dijkstra with max/*, or weights

Other relatives

  • Bidirectional Dijkstra searches from forwards and from backwards and stops when the frontiers' best combined distance cannot improve. On road networks it roughly halves the work; it is the query phase of contraction hierarchies.
  • Generalized semirings. Floyd-Warshall works for any closed semiring: (min, +) for shortest paths, (or, and) for reachability, (max, min) for widest paths. Dijkstra works for "monotone" path algebras where extending a path never makes it better — that is why bottleneck and probability variants work.
  • Minimum spanning trees look similar (Prim's algorithm is Dijkstra with key instead of ) but optimize a different objective: the total weight of a tree, not the distance from a source. Minimum Spanning Trees.

Practice ladder

Each problem is described in my own words; follow the link for the formal statement.

1. Network Delay Time (LeetCode 743) — A signal starts at one node of a weighted directed network; find when the last node receives it, or report that some never do. Teaches the basic heap Dijkstra and "max of distances".

Hint

Dijkstra from the source; the answer is max(dist) unless some distance is still infinite.

Solution
import heapq


def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = [float("inf")] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    ans = max(dist[1:])
    return -1 if ans == float("inf") else ans


assert network_delay_time([[1, 2, 5], [2, 3, 1], [1, 3, 9]], 3, 1) == 6
assert network_delay_time([[1, 2, 1]], 3, 1) == -1
print("network delay ok")

.

2. Path With Minimum Effort (LeetCode 1631) — Cross a height grid minimizing the largest height difference between consecutive cells. Teaches the bottleneck (minimax) variant of Dijkstra.

Hint

Path cost = max edge on the path. Dijkstra still works because extending a path never lowers its max: relax with max(d, |h[u] - h[v]|). Binary search + BFS, or Kruskal-style union-find, also work.

3. Path with Maximum Probability (LeetCode 1514) — Edges carry success probabilities; find the most reliable path. Teaches max-product Dijkstra.

Hint

Use a max-heap on probability (push negatives in Python) and relax with p * prob. Since every factor is , extending a path never increases its probability, which is the monotonicity Dijkstra needs.

4. Cheapest Flights Within K Stops (LeetCode 787) — Cheapest route using at most intermediate stops. Teaches edge-limited Bellman-Ford and the snapshot pitfall.

Hint

stops means at most edges. Run Bellman-Ford rounds, each relaxing from a copy of the previous round's distances.

Solution
def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        prev = dist[:]                     # snapshot: each round adds at most one edge
        for u, v, w in flights:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return -1 if dist[dst] == INF else dist[dst]


flights = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500], [0, 2, 300]]
assert find_cheapest_price(4, flights, 0, 3, 0) == 500
assert find_cheapest_price(4, flights, 0, 3, 1) == 400
assert find_cheapest_price(4, flights, 0, 3, 2) == 300
print("cheapest flights ok")

time, space.

5. Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334) — For each city count the others within a distance threshold; return the city with the fewest (largest index on ties). Teaches Floyd-Warshall on a small graph.

Hint

: run Floyd-Warshall, count per row, scan cities in increasing order using <= to keep the largest index on ties.

6. Minimum Cost to Make at Least One Valid Path in a Grid (LeetCode 1368) — Each cell has an arrow; following it is free, changing it costs 1. Teaches 0-1 BFS.

Hint

Edges to the arrow's neighbour weigh 0, to the other three neighbours 1. Deque: push 0-edges to the front, 1-edges to the back.

7. Number of Ways to Arrive at Destination (LeetCode 1976) — Count the shortest paths from 0 to modulo . Teaches counting on the shortest-path DAG inside Dijkstra.

Hint

When d + w < dist[v], set ways[v] = ways[u]; when d + w == dist[v], add ways[u]. This is correct because vertices are settled in distance order, so ways[u] is final when u is popped (weights are positive).

Solution
import heapq

MOD = 10**9 + 7


def count_paths(n: int, roads: list[list[int]]) -> int:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
    dist = [float("inf")] * n
    ways = [0] * n
    dist[0], ways[0] = 0, 1
    pq = [(0, 0)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v], ways[v] = nd, ways[u]
                heapq.heappush(pq, (nd, v))
            elif nd == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD
    return ways[n - 1]


assert count_paths(4, [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1], [0, 3, 3]]) == 2
assert count_paths(4, [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1], [0, 3, 2]]) == 3
assert count_paths(1, []) == 1
print("number of ways ok")

. Distances can exceed in this problem's constraints; Python integers are fine, use 64-bit elsewhere.

8. Shortest Routes I (CSES 1671) — Distances from city 1 to every city with cities and flights. Teaches Dijkstra at contest scale with 64-bit distances.

Hint

Lazy heap Dijkstra; long long distances; fast input. In Python, store (d, v) tuples and read everything with sys.stdin.buffer.

9. Shortest Routes II (CSES 1672) — Answer up to distance queries on a graph of 500 cities. Teaches when Floyd-Warshall beats repeated Dijkstra.

Hint

simple operations, then per query. Watch for parallel roads (keep the minimum) and use 64-bit.

10. Flight Discount (CSES 1195) — Cheapest route from 1 to when one flight may be taken at half price. Teaches the layered state graph.

Hint

State (city, coupon used?). From (u, 0) you can go to (v, 0) at full price or (v, 1) at half price; from (u, 1) only full price. Dijkstra over states. Alternative: Dijkstra from 1 forwards and from on the reversed graph, then try every edge as the discounted one.

Solution
import heapq


def flight_discount(n: int, flights: list[tuple[int, int, int]]) -> int:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for a, b, c in flights:
        adj[a].append((b, c))
    INF = float("inf")
    dist = [[INF, INF] for _ in range(n + 1)]
    dist[1][0] = 0
    pq = [(0, 1, 0)]
    while pq:
        d, u, used = heapq.heappop(pq)
        if d > dist[u][used]:
            continue
        for v, c in adj[u]:
            if d + c < dist[v][used]:
                dist[v][used] = d + c
                heapq.heappush(pq, (d + c, v, used))
            if not used and d + c // 2 < dist[v][1]:
                dist[v][1] = d + c // 2
                heapq.heappush(pq, (d + c // 2, v, 1))
    return min(dist[n])


assert flight_discount(3, [(1, 2, 3), (2, 3, 1), (1, 3, 7), (2, 1, 5)]) == 2    # 3 // 2 + 1
assert flight_discount(2, [(1, 2, 9)]) == 4
print("flight discount ok")

with two states per city.

11. High Score (CSES 1673) — Maximize the score of a walk from room 1 to room ; print if it can be made arbitrarily large. Teaches longest path via negated Bellman-Ford and "relevant" negative cycles.

Hint

Negate the weights. Run rounds, then mark every vertex still relaxable in further rounds. Answer only if a marked vertex is reachable from 1 and reaches (check with a DFS on the reversed graph). Cycles unrelated to the 1 → route do not matter.

12. Cycle Finding (CSES 1197) — Determine whether the graph has a negative cycle anywhere and print one. Teaches virtual-source Bellman-Ford and cycle recovery.

Hint

Initialize every distance to 0 (equivalent to a virtual source). If round relaxes vertex , step back times along parents, then collect the cycle.

Solution
def find_negative_cycle(n: int, edges: list[tuple[int, int, int]]) -> list[int] | None:
    dist = [0] * (n + 1)                   # virtual source: every vertex starts at 0
    parent = [0] * (n + 1)
    x = 0
    for _ in range(n):
        x = 0
        for a, b, c in edges:
            if dist[a] + c < dist[b]:
                dist[b] = dist[a] + c
                parent[b] = a
                x = b
    if x == 0:
        return None
    for _ in range(n):
        x = parent[x]
    cycle = [x]
    v = parent[x]
    while v != x:
        cycle.append(v)
        v = parent[v]
    cycle.append(x)
    return cycle[::-1]                     # printed as a closed walk: first == last


cyc = find_negative_cycle(4, [(1, 2, 1), (2, 4, 1), (3, 1, 1), (4, 1, -3), (4, 3, -2)])
assert cyc is not None and cyc[0] == cyc[-1]
w = {(1, 2): 1, (2, 4): 1, (3, 1): 1, (4, 1): -3, (4, 3): -2}
assert sum(w[(a, b)] for a, b in zip(cyc, cyc[1:])) < 0
assert find_negative_cycle(3, [(1, 2, 5), (2, 3, -1)]) is None
print("cycle finding ok")

.

13. Investigation (CSES 1202) — For the cheapest route from 1 to , report its price, the number of cheapest routes, and the minimum and maximum number of flights among them. Teaches DP on the shortest-path DAG.

Hint

During Dijkstra, keep ways, minEdges, maxEdges per vertex, updated on strict improvement (reset) and on ties (combine). All weights are positive, so a vertex's tallies are final when it is popped.

14. Flight Routes (CSES 1196) — Print the cheapest route prices from 1 to (routes may revisit cities). Teaches k shortest walks by popping each vertex up to times.

Hint

Keep a pop counter per vertex. Pop (d, u); if u was already popped times, skip; otherwise record and relax all edges unconditionally (push d + w). The pops of come out in non-decreasing order.

15. Dijkstra? (Codeforces 20C) — Print a shortest path in an undirected weighted graph, or . Teaches parent pointers, 64-bit distances and the classic anti-slow-Dijkstra tests.

Hint

Lazy Dijkstra with the stale check (tests include inputs that make implementations without it time out), 64-bit sums, parent array, reverse at the end.

Common mistakes & interview follow-ups

"Why doesn't Dijkstra work with negative edges?" Give the three-vertex counterexample and point to the line of the proof that uses non-negativity: "the rest of the path from the frontier to has weight ."

"Can you make Dijkstra work with negative edges by re-adding vertices?" Correct without negative cycles, but exponential in the worst case; mention Johnson's reweighting as the principled fix.

"Decrease-key or lazy deletion?" Same bound. Lazy is simpler, works with standard heaps, and is usually as fast or faster; decrease-key bounds the heap at entries, which matters when memory is tight.

"The graph is dense. Still a heap?" No: the array version is better when .

"Distances from every vertex to one target?" Reverse all edges and run once from the target.

"Shortest path visiting a set of required vertices?" For required vertices: Dijkstra from each to get pairwise distances, then a bitmask DP over subsets () — this is a small travelling salesman problem, NP-hard in general.

Common mistakes interviewers watch for: marking visited on push; no stale check; 32-bit overflow; Dijkstra with negative weights; wrong Floyd-Warshall loop order; k-stops without a snapshot; unreachable target returned as infinity.

Quick quiz

1. In the Dijkstra trace, why is the entry (4, A) still in the heap after A has been settled at 3, and what happens to it?

Answer

Lazy deletion never removes the old entry when dist[A] drops from 4 to 3; it pushes a new one. When (4, A) is popped, 4 > dist[A] = 3, so it is skipped as stale.

2. Bellman-Ford with edges in topological order of a DAG: how many rounds until nothing changes?

Answer

One round makes every distance exact (it is the DAG DP), and a second round confirms that nothing changes. In the trace example, scanning in the order S→A, S→B, B→A, … finishes in round 1 and confirms in round 2.

3. After Floyd-Warshall, . What does that tell you, and is trustworthy?

Answer

Vertex 2 lies on a negative cycle. is in truth if 0 can reach 2 and 2 can reach 5 ( and ); otherwise it is unaffected by that cycle.

4. With potentials , what is the reweighted cost of edge 1→2 (original weight ), and why is it allowed to be 0?

Answer

. Zero is non-negative, which is all Dijkstra needs. Edges on shortest paths from the virtual source always get reduced weight exactly 0.

5. On an 8-neighbour grid with diagonal cost , a teammate uses Manhattan distance as the A* heuristic. What goes wrong?

Answer

Manhattan overestimates: one diagonal move costs but Manhattan counts 2. The heuristic is inadmissible, so A* can return a suboptimal path. Use octile distance.

Further reading / sources

  • E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1:269–271, 1959.
  • Richard Bellman, "On a routing problem", Quarterly of Applied Mathematics 16:87–90, 1958; L. R. Ford Jr., "Network flow theory", RAND paper P-923, 1956; E. F. Moore, "The shortest path through a maze", 1959.
  • Robert W. Floyd, "Algorithm 97: Shortest path", Communications of the ACM 5(6):345, 1962; Stephen Warshall, "A theorem on Boolean matrices", Journal of the ACM 9(1):11–12, 1962.
  • Donald B. Johnson, "Efficient algorithms for shortest paths in sparse networks", Journal of the ACM 24(1):1–13, 1977; and "A note on Dijkstra's shortest path algorithm", Journal of the ACM 20(3), 1973 (the exponential behaviour with negative edges).
  • P. E. Hart, N. J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths", IEEE Transactions on Systems Science and Cybernetics 4(2):100–107, 1968.
  • Jin Y. Yen, "Finding the k shortest loopless paths in a network", Management Science 17(11):712–716, 1971; David Eppstein, "Finding the k shortest paths", SIAM Journal on Computing 28(2):652–673, 1998.
  • Michael L. Fredman and Robert E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM 34(3), 1987.
  • Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling, "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks", Experimental Algorithms (WEA 2008), LNCS 5038, pp. 319–333.
  • M. Chen, R. A. Chowdhury, V. Ramachandran, D. Lan Roche, L. Tong, "Priority Queues and Dijkstra's Algorithm", UT Austin technical report TR-07-54, 2007.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed.: chapter 24 (single-source: Bellman-Ford 24.1, DAGs 24.2, Dijkstra 24.3, difference constraints 24.4, proofs 24.5) and chapter 25 (all pairs: Floyd-Warshall 25.2, Johnson 25.3).
  • Sedgewick and Wayne, Algorithms, 4th ed., section 4.4 "Shortest Paths".
  • cp-algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS, Finding a negative cycle.
  • R. Duan, J. Mao, X. Mao, X. Shu, L. Yin, "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths", STOC 2025; A. Bernstein, D. Nanongkai, C. Wulff-Nilsen, "Negative-Weight Single-Source Shortest Paths in Near-linear Time", FOCS 2022.

Previous lesson: Topological Sort & DAG DP · Next lesson: Union-Find in Depth

Related: Graphs overview · BFS in Depth · Heaps & Priority Queues · Minimum Spanning Trees · Network Flow · Network Layer · BGP · Spatial Indexing · Greedy Algorithms · Course home