Bellman–Ford, negative cycles and Floyd–Warshall
Connection and contract
Use the Dijkstra relaxation lesson and DP state design. Work on a directed weighted graph; weights may be negative. A walk may repeat vertices and edges. If a source can reach a negative-total-weight cycle, vertices reachable from that cycle have no finite minimum walk weight: repeat the cycle to reduce weight without bound. This does not automatically affect vertices that cannot be reached from that cycle. An unreachable negative cycle does not invalidate finite shortest distances from this source.
1. Bellman–Ford as edge-bounded DP
Let B_k[v] be the minimum weight of a source-to-v walk using at most k edges. Initialize B_0[s]=0 and B_0[v]=∞ otherwise. Using separate previous and current arrays:
B_k[v]=min(B_(k−1)[v], min over edges (u,v) of B_(k−1)[u]+w(u,v)), with finite-predecessor guards.
Any walk with at most k edges either already uses at most k−1 or ends in some edge (u,v). This proves the recurrence. If no source-reachable negative cycle exists, a shortest walk can have cycles removed without increasing weight, leaving a simple path with at most V−1 edges. Therefore V−1 passes suffice.
Common Bellman–Ford code instead relaxes all edges in place each pass. It can propagate several edges within one pass, depending on edge order; do not claim its intermediate array equals B_k exactly. Nevertheless, after k passes it is no worse than the edge-bounded optimum for at most k edges, and V−1 passes still suffice when a finite shortest solution exists. If a full pass makes no improvement, stop early.
2. Worked passes and cycle test
Edges s→a=4,s→b=5,a→b=−2. With separate-array passes: B_0=(0,∞,∞); B_1=(0,4,5); B_2=(0,4,2). The final path to b is s,a,b, cost 2. In-place order s→a,a→b,s→b can reach b=2 in its first pass, illustrating the difference.
After V−1 full relaxation passes, scan once more. If an edge with finite d[u] satisfies d[u]+w(u,v)<d[v], a negative cycle reachable from s exists. The finite guard excludes disconnected negative cycles. This scan detects existence; it does not mean every vertex has distance −∞. To classify affected vertices, collect endpoints of still-relaxable edges after the standard passes and traverse outgoing edges from them: those reachable vertices are downstream of a reachable negative cycle. Parent tracking plus V backward predecessor steps can help locate a cycle, but detection alone does not supply a trustworthy printed cycle without reconstruction logic.
Example s→a=1,a→b=1,b→a=−3,b→t=2 and isolated-from-s x→x=−1. Cycle a→b→a has weight −2 and is reachable, so a,b,t have no finite minimum. s remains 0 if there is no route back to it. The x cycle is unreachable from s and does not change s's distances to other vertices. Self-loops are allowed in this lesson's directed graph model.
3. Floyd–Warshall uses intermediate vertices
For all-pairs distances number vertices 1,...,V. Let D^(k)[i,j] be the minimum walk/path weight with internal vertices drawn from {1,...,k}, in the absence of a relevant negative cycle. Initialize D^(0)[i,i]=0 and D^(0)[i,j] to the least direct edge weight, or ∞ if absent; take the minimum with 0 on the diagonal so a negative self-loop is retained. For each k:
D^(k)[i,j]=min(D^(k−1)[i,j], D^(k−1)[i,k]+D^(k−1)[k,j]).
Either a shortest path avoids k, or split it at k into two paths using only earlier internal vertices. The standard in-place implementation loops k outermost, then i and j, with finite checks before addition. It is not an edge-count DP. With a→b=3,b→c=−1,a→c=7, the stage allowing b changes a→c to 2.
4. Negative cycles, costs and traps
After Floyd–Warshall, a negative diagonal D[k,k]<0 detects a negative cycle. Pair (i,j) has unbounded-below distance precisely when i can reach some negative-cycle vertex k and k can reach j; unaffected pairs may retain finite distances or ∞. Raw negative-cycle-affected matrix entries are not valid finite shortest distances.
Bellman–Ford takes O(VE) time for passes (plus O(V) initialization) and O(V) distance/parent auxiliary storage; a separate-array version still uses O(V). Floyd–Warshall takes Θ(V³) time and Θ(V²) matrix storage. No negative cycles does not mean Dijkstra is valid: negative edges alone can invalidate it. Guard infinity arithmetic, distinguish source-reachable from global cycles, and keep Floyd's k loop outside the pair loops.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Without source-reachable negative cycles, Bellman–Ford needs at most how many full passes?
A. 1 always B. V−1 C. E−1 always D. V²
Answer: B
A: One pass may not propagate all paths.
B: A simple shortest path uses at most V−1 edges.
C: Edge count does not give the standard pass guarantee.
D: Quadratically many passes are unnecessary.
P02. An extra relaxable edge proves a source-reachable negative cycle only with which guard?
A. d[u] is finite B. w(u,v) is positive C. u is source D. Graph is complete
Answer: A
A: Only reachable predecessors may relax.
B: Negative edges can participate.
C: Cycle can be far from the source.
D: Completeness is irrelevant.
P03. s→a=4,s→b=5,a→b=−2: separate-array B_1[b],B_2[b]?
A. 2,2 B. 5,2 C. 5,5 D. ∞,2
Answer: B
A: The two-edge route is not allowed in B_1.
B: One edge gives 5, two permit 4−2=2.
C: The second pass improves through a.
D: A direct one-edge route exists.
P04. Floyd–Warshall stage k allows which change?
A. At most k edges B. Vertex k as an additional internal vertex C. Only source k D. Only paths of exactly k weight
Answer: B
A: That describes edge-bounded DP, not Floyd.
B: Intermediate-vertex set expands by k.
C: All source-target pairs are considered.
D: k is a vertex index, not a path weight.
P05. After Floyd–Warshall, what detects a negative cycle?
A. Any negative off-diagonal entry B. A negative diagonal entry C. Any infinite entry D. All diagonal entries zero
Answer: B
A: A single negative edge can give this without a cycle.
B: D[k,k]<0 is a negative closed-walk signal.
C: Infinity means lack of reachability.
D: Zero diagonals alone do not signal a negative cycle.
P06. Which vertices lose finite shortest distances due to a reachable negative cycle?
A. Every vertex automatically B. Only the source C. Vertices reachable onward from that cycle D. Only vertices with negative outgoing edges
Answer: C
A: Other components or upstream vertices may be unaffected.
B: The source may not be reachable back from the cycle.
C: Repeat the cycle then follow a route to those vertices.
D: A downstream vertex can have no outgoing edges.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in