Unit 3.6 · about 5 h
109 / 324Dijkstra, Bellman-Ford and negative cycles
Nonneg weights buy a heap-ordered greedy; negative edges or hop budgets need repeated relaxation instead. Picking by weight profile, not by habit, is the whole unit.
- derive
- implement
You can now
- Implement lazy-deletion Dijkstra on heapq, state the stale-entry check, and name the nonneg-weight assumption it depends on.
- Prove the settle-once invariant from nonnegativity, and exhibit the wrong answer a settled variant locks in with one negative edge.
- Implement Bellman-Ford with \(V - 1\) passes, \(V\)th-pass negative-cycle detection and the snapshot variant for \(K\)-edge budgets.
Covers
- Dijkstra relaxation, stale priorities and nonnegative weights
- Negative edges, Bellman-Ford and negative-cycle detection
Study, in this order
3 steps
- Dijkstra's shortest-path algorithmDSA Handbook - graphs
The operations: pop, lazy-skip, relax, settle; Lazy deletion: pushing duplicates instead of decrease-key; Worked example with the two stale-skip events
- Bellman-Ford and negative cyclesDSA Handbook - graphs
The algorithm, in three pieces; Why V minus 1 is the right number; Bellman-Ford with a budget: LC 787 with the snapshot line; Detecting a negative cycle
Depth · Skim SPFA as a practical mention only; vanilla Bellman-Ford is the expected interview answer.
- Shortest Paths, Chapter 8Algorithms - graph chapters
8.1 Shortest Path Trees, 8.2 Negative Edges and 8.3 The Only SSSP Algorithm; 8.5 Directed Acyclic Graphs; 8.6 Best-First: Dijkstra's Algorithm with No Negative Edges; 8.7 Relax ALL the Edges: Bellman-Ford (printed pp. 274-296)
Focus on
- heapq has no decrease-key (check
hasattron the course Python:False), so this card uses the lazy-deletion variant: push a fresh entry per relaxation and skip withif d > dist[u]: continue. Count the skips; the handbook graph produces exactly 2. - Settle-once holds only for nonneg weights: every undiscovered alternative path must leave through an unsettled vertex of distance at least \(d\), so adding nonneg remainders cannot beat \(d\). One negative edge breaks the argument and the code stays silent.
- Bellman-Ford's pass \(i\) is correct for paths of at most \(i\) edges by induction, and simple paths use at most \(V - 1\) edges. The \(V\)th pass is the detector, not bookkeeping: any relaxation there proves a reachable negative cycle.
- \(K\)-edge budgets read from the previous pass:
snapshot = dist[:]each round. Reading livedistchains two edges in one pass and silently spends budget twice.
Reproduce closed-book
[0,7,9,20,20,11] with exactly 2 stale skips (7 pushes, 8 pops). A settle-once variant on edges [(0,1,6),(0,2,7),(2,3,-3),(3,1,-2)] locks dist[1] at 6 while Bellman-Ford reports the true 2. LC 787's sample (\(n = 4\), \(k = 1\)) returns 700 with the snapshot line and the wrong 400 without it.Traps
- Negative input to Dijkstra: no exception, no warning, wrong distances. Scan weights for negatives first; one negative edge reroutes to Bellman-Ford.
- \(K\) stops means \(K + 1\) edges: a direct flight is 0 stops and 1 edge. Running \(K\) passes under-relaxes by one hop.
- Missing
INFguard beforedist[u] + w: in Java and C++INT_MAXpluswwraps negative and relaxes the unreachable. Gate ondist[u] != INF; Python with float inf is exempt but keep the guard for portability.
Practice
LeetCode 743: Network Delay Time
The three listed examples (times [[2,1,1],[2,3,1],[3,4,1]] with \(n = 4\) and \(k = 2\); single edge; unreachable node)
Attempt cold per the AlgoMaster pool note. Lazy-deletion heap with the stale check; answer is max dist or -1. After-attempt reference is DSA Handbook 8.9.
LeetCode 787: Cheapest Flights Within K Stops
Sample (\(n = 4\), five flights, src 0, dst 3, \(k = 1\) answers 700)
Bellman-Ford with \(K + 1\) snapshot passes, not Dijkstra: the hop constraint breaks settle-once. After-attempt reference is DSA Handbook 8.10.
Self-test
-
Prove the settle-once claim.
Let \(u\) pop with the smallest tentative distance \(d\). Take any source-to-\(u\) path and let \(y\) be its first vertex outside the settled set. Its predecessor \(x\) was settled with an exact distance (induction) and relaxed \((x, y)\), so the prefix up to \(y\) costs at least \(\operatorname{dist}[x] + w(x, y) \ge \operatorname{dist}[y]\), and \(\operatorname{dist}[y] \ge d\) because \(u\) popped first. The rest of the path adds nonnegative weight, so no path beats \(d\) and \(\operatorname{dist}[u]\) is final. -
Prove \(V - 1\) passes suffice for Bellman-Ford.
Induction: pass 1 fixes all one-edge shortest paths from direct relaxations; if pass \(i - 1\) fixed all paths of at most \(i - 1\) edges, pass \(i\) extends each by one scanned edge. Simple shortest paths repeat no vertex, hence use at most \(V - 1\) edges. -
Why does the no-snapshot LC 787 code return 400 instead of 700?
Without thesnapshotthe first pass already chains edges:(0,1)setsdist[1] = 100, then(1,2)reads it and setsdist[2] = 200, then(2,3)setsdist[3] = 400, three edges against a two-edge budget. Thesnapshotmakes every pass extend only the previous pass's distances. -
When is 0-1 BFS the right call over Dijkstra?
All weights in \(\{{0, 1\}}\): push front on 0-cost, back on 1-cost relaxations. Thedequefront always holds minimum tentative distance, so each operation is \(O(1)\) and total is \(\Theta(V + E)\) instead of heap-logged.
Completion criterion
Stop when
Your blank-file script prints [0,7,9,20,20,11] with 2 stale skips, the 6-versus-2 negative-edge gap and the 700-versus-400 snapshot gap, and both LeetCode problems pass with the assumption stated before the import.
Leads to
- 3.7 Minimum spanning trees with Kruskal and Prim Prim reuses the frontier heap with one substitution: edge weight to the tree instead of path distance from the source.
- 5.9 Dynamic programming as shortest paths, formulations and limits Bellman-Ford is dynamic programming over edge count; carry the relaxation-as-DP frame into recurrences.
Comes after
- 2.6 Heaps and priority queuesDijkstra consumes a priority queue with stale entries.
- 3.2 BFS, unweighted shortest paths and connected componentsReplace the FIFO with a heap when edges stop costing the same.
- 3.4 Topological ordering and strongly connected componentsDAG shortest paths relax vertices in topological order, which is why order comes before weights.
- 5.8 Recurrence proofs and differential validationProve relaxation invariants with the same induction shape.
- 5.9 Dynamic programming as shortest paths, formulations and limitsRead the Bellman-Ford DP formulation as the same recurrence on graphs.
Resources for this unit
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
Also in this section
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.