The Bellman–Ford unit handles arbitrary real edge weights by repeated relaxation rounds, and the 0–1 BFS unit exploits weights in . This unit treats the two most commonly used general algorithms for the remaining cases. Dijkstra's algorithm computes distances from one source when all weights are nonnegative and is much faster than Bellman–Ford. Floyd–Warshall computes the distances between all ordered pairs of vertices by dynamic programming over a set of allowed intermediate vertices. Both depend on the same basic fact: a shortest path is built from shortest paths.
1. Setting and conventions
Definition 16.3.1
(Distance and relaxation)
Let be a finite directed graph with vertices and edges, and let assign each edge a weight. A walk has weight equal to the sum of its edge weights, and is the minimum weight of a walk from to , or if there is none. When the graph is undirected, replace each edge by two directed edges of the same weight. Parallel edges and self-loops are allowed.
Relaxation. Given a tentative label for every vertex, relaxing an edge performs: if , set . Throughout, every finite label is the weight of a real walk from the source, so always.
Optimal substructure. If is a minimum-weight walk to , then each prefix is a minimum-weight walk to ; otherwise replacing the prefix by a lighter walk would lighten the whole walk.
2. Dijkstra's algorithm
Hypothesis. Every edge weight satisfies . Fix a source .
The algorithm maintains labels and a set of settled vertices. It repeatedly takes an unsettled vertex with the smallest finite label, settles it, and relaxes all edges from to unsettled vertices; a settled label is never changed again. With a binary min-heap, the usual implementation stores pairs (label, vertex) and discards stale entries when they are removed.
for each v: d[v] = infinity; settled[v] = false
d[s] = 0
H = min-heap containing (0, s)
while H is not empty:
(k, u) = extract_min(H)
if settled[u] or k != d[u]: continue # stale entry
settled[u] = true
for each edge (u, v, w):
if not settled[v] and d[u] + w < d[v]:
d[v] = d[u] + w
insert (d[v], v) into H
return d
Definition 16.3.2
(Settled vertex and stale entry)
A vertex is settled once it has been extracted from the heap with a key equal to its current label ; from then on is never changed. A heap entry is stale if is already settled or , and stale entries are discarded without any relaxation.
Theorem 16.3.3
(Correctness of Dijkstra's algorithm)
If all weights are nonnegative, then when a vertex is settled, . At termination, for every vertex , including for unreachable ones.
Proof
(Induction on the order of settling)
We show that the claim holds for each vertex at the moment it is settled, by induction on the order of settling. The first settled vertex is with , since a nonnegative graph has no walk of negative weight.
Suppose is settled next, with label , and all earlier settled vertices are correct. Since is the weight of some walk, . Suppose for contradiction . Then ; take a minimum-weight walk from to and let be the first vertex on that is not settled just before is settled. It exists because itself is unsettled, and it is not , so it has a predecessor on that is settled. By the induction hypothesis , and when was settled the edge was relaxed, so afterwards . The prefix of up to is a minimum-weight walk to by optimal substructure, so . Hence , and with we get . Because the remainder of from to has nonnegative weight, . So the unsettled vertex has a finite label smaller than , and the heap contains a current entry for with key . That contradicts the choice of as the entry of smallest key (if the contradiction is immediate: ). Hence .
Every vertex reachable from is eventually settled: otherwise some edge on a path from has settled and unsettled and reachable, and relaxing it when was settled gave a finite label and a heap entry, which would be extracted before the heap empties. Unreachable vertices never receive a finite label.
Proof X-ray
Where the proof uses nonnegativity
The proof has one non-obvious move: instead of comparing with every vertex, it follows a minimum-weight walk and stops at the first unsettled vertex . Three facts meet at this frontier vertex. (1) Its predecessor is settled, so by the induction hypothesis. (2) The edge was relaxed when was settled, so , the last equality by optimal substructure. (3) The tail of from to has weight at least , so . Facts (1) and (2) never look at the sign of a weight; only (3) needs . Together they give , so the heap would have returned before , a contradiction. Without nonnegativity the chain breaks exactly at (3), and the input in the negative-edge section below has .
Proposition 16.3.4
(Cost of Dijkstra with a binary heap)
Dijkstra's algorithm with lazy deletion and a binary min-heap inserts at most heap entries, runs in time and uses space.
Proof
(Counting settlements and heap entries)
Each vertex is settled once, so each edge is relaxed at most once. Every successful relaxation inserts one heap entry, so the heap receives at most entries, and each insertion or extraction costs . Total time is , which is when and the graph has no parallel edges. Space is . An array scan instead of a heap gives , which is preferable for very dense graphs.
3. Worked example: Dijkstra with stale entries
Worked example 16.3.5
(Dijkstra with stale heap entries)
Edges: (4), (1), (2), (1), (5), (3), (6).
| Extracted | Action | Heap afterwards |
|---|---|---|
| settle ; , | ||
| settle ; improves ; | ||
| settle ; improves ; | ||
| stale, already settled | ||
| settle ; improves | ||
| stale | ||
| settle | ||
| stale | empty |
The distances are , , (through , not the direct edge of weight 4), and , via .
4. Why negative edges break Dijkstra
Counterexample mode
A negative edge defeats Dijkstra
Claim: if the graph has no negative cycle, Dijkstra's algorithm returns correct distances even when some edge weights are negative.
Take edges (2), (3), (−2). Dijkstra settles , then with label 2, then with label 3. The edge would give , but is already settled and its label is never revisited, so the output is . The true distance is . In the proof, the walk is the path whose unsettled vertex has : the tail has negative weight, so the inequality fails. Adding a constant to every weight to remove negatives does not repair the problem, because paths with more edges are penalized more.
The corrected statement keeps the hypothesis . When weights may be negative but no negative cycle exists, use Bellman–Ford, or Floyd–Warshall below for all pairs.
5. Floyd–Warshall
Definition 16.3.6
(Shortest paths with restricted intermediates)
Number the vertices . Define as the minimum weight of a simple path from to whose intermediate vertices all lie in (with for the empty path), or if none exists. The case allows no intermediate vertex:
keeping the smallest weight among parallel edges. Hypothesis: has no negative cycle (negative weights themselves are allowed).
Theorem 16.3.7
(Floyd–Warshall recurrence)
If has no negative cycle, then for every and all vertices ,
Proof
(Splitting a path at the vertex k)
Consider a minimum-weight simple path from to with intermediates in . If is not an intermediate vertex of , then is counted by . If it is, it occurs exactly once because is simple, and splitting at gives a simple path and a simple path , each with intermediates in ; by optimal substructure their weights are and . Conversely each of the two expressions is the weight of an actual walk with intermediates in , and since there is no negative cycle, a minimum-weight such walk can be taken simple (deleting a cycle never increases weight). So the minimum of the two expressions is exactly .
At , .
D = D0
for k = 1..n:
for i = 1..n:
for j = 1..n:
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
One matrix suffices. In round , row and column do not change: would change only if , i.e. , and when there is no negative cycle. So reading the in-place values gives the same results as reading . Time is and space , independent of . For a graph with no negative cycle that is dense, this is comparable to running Dijkstra from each source; with negative weights it is the simple choice.
Concept lensAlgebraic
All-pairs distances as a min-plus matrix power
Define . Since has zero diagonal, is the least weight of a walk from to with at most edges. With no negative cycle, shortest walks may be taken simple, so . Floyd–Warshall reaches the same matrix by letting intermediate vertices in one at a time.
If a negative cycle is present, it is standard that some diagonal entry becomes negative; this is the usual test, though entries may become unreliable, so a negative diagonal means "stop, distances through that cycle are undefined".
6. Worked example: Floyd–Warshall with a negative edge
Worked example 16.3.8
(Floyd–Warshall with a negative edge)
Vertices with edges (3), (8), (−2), (6), (1), (5). The only cycle through all four is with weight , and the other cycles are likewise positive, so the hypothesis holds. Rows are .
: row 1 ; row 2 ; row 3 ; row 4 .
: only has finite. , . Row 4 .
: column 2 is finite for with values ; row 2 is . , , , stays 0.
: column 3 is for ; row 3 is . , , stays 0.
: column 4 is ; row 4 is . : , , . Row 2: , , . Row 3: , , .
Final matrix: row 1 ; row 2 ; row 3 ; row 4 . Check : the only route out of 3 is with weight .
Worked example 16.3.9
(A negative cycle appears on the diagonal)
Vertices with (1) and (−3), a cycle of weight . . At : . The negative diagonal entry reveals the cycle.
7. Common mistakes
Common mistake
(A negative edge without a negative cycle)
Dijkstra's hypothesis is on every edge, not merely the absence of negative cycles. The acyclic graph (2), (3), (−2) has no cycle at all, yet Dijkstra reports instead of . Use Bellman–Ford, or Floyd–Warshall for all pairs.
Common mistake
(Settling a vertex when it is first discovered)
A label is final only when its entry is extracted with the smallest current key, not when the vertex is first reached: a vertex settled later may offer a lighter route. In the first worked example, is reached with label but ends with .
Common mistake
(The loop over k must be outermost)
The Floyd–Warshall invariant concerns the set of allowed intermediates, so every pair must be updated for before is admitted. With innermost, a pair is finished before later intermediates have been combined, and paths that need several intermediates can be missed.
Three further slips to check:
- Forgetting to skip stale heap entries, which wastes work and distorts operation counts.
- Adding when is a finite sentinel: test that both operands are finite first.
- Reporting a Floyd–Warshall matrix as valid without checking the diagonal for negative entries when the input may contain a negative cycle.
Exercises
Quick check
(Run Dijkstra from on edges (2), (5), (1), (7), (2). Give the settling order and the final distances.)
Each improvement creates a new heap entry; the older entry becomes stale.
Solution · Answer
Extract : , . Extract : improves to , . Extract : improves to . Extract is stale; extract : settle ; the entry is stale. Settling order . Distances: , , , (path ).
Quick check
(Edges: (1), (4), (−5). What does Dijkstra output for , and what is ?)
Check what happens to the edge when is settled.
Solution · Answer
Dijkstra settles (, ), then with label 1 (no outgoing edges), then with label 4. The edge is ignored because is settled, so the output is . But the walk has weight , so and Dijkstra is wrong here.
Quick check
(A graph has vertices and no edges. What does Dijkstra from insert into the heap, and what does it return?)
Count how many relaxations can ever happen.
Solution · Answer
Only the initial entry is inserted. It is extracted and settles ; there are no edges to relax, so the heap becomes empty. The output is and for every other vertex, which is correct because no other vertex is reachable. This is the case of the bound of insertions.
Exercise 16.3.10
(Run Floyd–Warshall on vertices with edges (4), (5), (−1), (2). Give the final matrix.)
Core
Solution(3)
- 1
Write the initial matrix
: row 1 , row 2 , row 3 . (The cycle has weight .)
- 2
Rounds and
: only row 3 has finite : , . Row 3 .
: column 2 is ; row 2 is . ; .
- 3
Round and the answer
: column 3 is ; row 3 is . , ; , .
Final: row 1 , row 2 , row 3 . Check via .