Worked examples — Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE)

---

The scenario matrix

Every Bellman-Ford problem lands in one of these cells. Our examples below are labelled with the cell they hit, so together they cover the whole table.

#	Case class	What's special	Example
A	All-positive edges	Dijkstra would also work; sanity baseline	Ex 1
B	Negative edge, no cycle	The reason Bellman-Ford exists	Ex 2
C	Order matters in a pass	Bad edge order needs full $V-1$ passes	Ex 3
D	Negative cycle reachable from source	Detection must fire	Ex 4
E	Negative cycle not reachable from source	Detection must stay silent	Ex 5
F	Unreachable vertex ($\infty$)	The dist[u] != inf guard	Ex 6
G	Degenerate: 1 vertex, 0 edges	Base case only	Ex 7
H	Zero-weight cycle (limiting between $-$ and $+$)	Must not be flagged	Ex 8
I	Real-world word problem	Currency / travel tolls	Ex 9
J	Exam twist: "which pass first settles $v$?"	Reasoning about convergence speed	Ex 10

Note the two limiting boundaries we deliberately test: cell H sits exactly on the fence (cycle sum $=0$, neither negative nor positive) and cell G is the smallest legal graph. Never skip the boundaries — that is where wrong code dies.

---

Ex 1 — Cell A: all-positive baseline

Forecast: guess the four final numbers before reading on. (Hint: is going $0\to 1\to 2$ cheaper than $0\to 2$ direct?)

1. Init. dist = [0, ∞, ∞, ∞]. Why this step? With $0$ edges you can only sit at the source, cost $0$; everything else is unknown, i.e. $\infty$.
2. Pass 1, edges in listed order.
   • $0\to 1$: $0+2=2<\infty$ → dist[1]=2.
   • $0\to 2$: $0+6=6<\infty$ → dist[2]=6.
   • $1\to 2$: $2+3=5<6$ → dist[2]=5. (the detour wins!)
   • $1\to 3$: $2+5=7<\infty$ → dist[3]=7.
   • $2\to 3$: $5+1=6<7$ → dist[3]=6. Why this step? One sweep already propagated cost outward two hops because the edges happened to be in a friendly order.
3. Pass 2. Check every edge again → nothing improves. Why this step? When a full pass changes nothing, the early-exit break fires; distances are final.

Answer: dist = [0, 2, 5, 6].

Verify: Cheapest to $2$ is $0\to 1\to 2=2+3=5$ (beats direct $6$). Cheapest to $3$ is $0\to 1\to 2\to 3=5+1=6$ (beats $0\to 1\to 3=7$). ✓

---

Ex 2 — Cell B: negative edge, no cycle

Forecast: the road $1\to 2$ pays you $3$. Does that make reaching $2$ cheaper than the direct $5$?

1. Init. dist = [0, ∞, ∞, ∞].
2. Pass 1.
   • $0\to 1$: dist[1]=4.
   • $0\to 2$: dist[2]=5.
   • $1\to 2$: $4+(-3)=1<5$ → dist[2]=1. Why? the negative edge undercuts the direct route.
   • $2\to 3$: $1+2=3<\infty$ → dist[3]=3.
3. Pass 2. No edge improves → converged. Why this step? Confirms nothing negative loops back; this is a legit finite answer.

Answer: dist = [0, 4, 1, 3].

Verify: $0\to 1\to 2=4-3=1$; then $\to 3=1+2=3$. No cycle exists (edges only go "forward"), so distances are meaningful. ✓ This is the exact scenario Dijkstra would mishandle, because it would finalize dist[2]=5 before ever seeing the cheaper negative-edge route — see Dijkstra's Algorithm.

---

Ex 3 — Cell C: edge order forces multiple passes

Forecast: same final answer as Ex 2 — but how many passes until it settles now?

1. Pass 1 (this bad order):
   • $2\to 3$: dist[2] is $\infty$ → guard blocks it, no change.
   • $1\to 2$: dist[1] is $\infty$ → blocked.
   • $0\to 2$: $0+5<\infty$ → dist[2]=5.
   • $0\to 1$: $0+4<\infty$ → dist[1]=4. Result after pass 1: [0, 4, 5, ∞]. Why worse? The edges that use new info came before the edges that produced it.
2. Pass 2.
   • $2\to 3$: $5+2=7<\infty$ → dist[3]=7.
   • $1\to 2$: $4-3=1<5$ → dist[2]=1.
   • $0\to 2$, $0\to 1$: no change. Result: [0, 4, 1, 7].
3. Pass 3.
   • $2\to 3$: $1+2=3<7$ → dist[3]=3. Result: [0, 4, 1, 3]. Now it matches Ex 2.

Answer: dist = [0, 4, 1, 3] — identical, but it needed 3 passes ($=V-1$) instead of 1.

Verify: Same numbers as Ex 2 ✓. This is why we never trust a lucky order: worst case needs the full $V-1=3$ passes. The final answer is order-independent; the speed is not.

---

Ex 4 — Cell D: negative cycle reachable → DETECT

Forecast: loop $0\to 1\to 2\to 0$ sums to $1-1-1=-1$. Can any finite answer survive?

1. Init. dist = [0, ∞, ∞]. Here $V=3$, so we do $V-1=2$ settle passes.
2. Pass 1. $0\to 1$: dist[1]=1. $1\to 2$: $1-1=0$ → dist[2]=0. $2\to 0$: $0-1=-1<0$ → dist[0]=-1. Why this step? The cycle already dragged the source's own cost below zero — a red flag.
3. Pass 2. Everything drops again: dist[1]=0, dist[2]=-1, dist[0]=-2. Why this step? Each lap of the loop subtracts $1$; the values never stop.
4. Extra pass (the $+1$). $2\to 0$: still relaxes ($-1-1=-2<-2$? recompute with current) → some edge still improves. Why this step? After $V-1$ passes everything that can settle has settled. A still-relaxable edge can only mean a negative cycle.

Answer: return None — negative cycle reachable from source.

Verify: Cycle weight $=1+(-1)+(-1)=-1<0$. Looping it $k$ times gives cost $\to -\infty$, so no finite shortest distance exists → the flag is correct, not the numbers. See Negative Weight Cycles. ✓

---

Ex 5 — Cell E: negative cycle NOT reachable → stay silent

Forecast: there is a negative cycle in the graph. Will Bellman-Ford flag it?

1. Init. dist = [0, ∞, ∞, ∞].
2. All passes. Only $0\to 1$ ever relaxes (dist[1]=2). Edges $2\to 3$ and $3\to 2$ have dist[2]=dist[3]=∞ → guard blocks them forever. Why this step? Source $0$ has no path into $\{2,3\}$, so their distances stay $\infty$ and the loop is never entered.
3. Extra pass. No edge relaxes → no cycle reported.

Answer: dist = [0, 2, ∞, ∞]. Cycle not detected.

Verify: Bellman-Ford only detects cycles reachable from the source — this is the second parent-note mistake made concrete. To catch all cycles you'd add a virtual source with $0$-weight edges to every vertex (then $2,3$ become reachable). ✓

---

Ex 6 — Cell F: the dist[u] != inf guard in action

Forecast: without the guard, would that huge $-100$ edge corrupt dist[1]?

1. Init. dist = [0, ∞, ∞].
2. Relax $0\to 1$: dist[1]=3.
3. Relax $2\to 1$: dist[2] is $\infty$. Computing $\infty +(-100)$ is still $\infty$, and $\infty <3$ is false, so no change even without a guard in Python — but in a fixed-width integer language, "INF + (−100)" can wrap around to a huge negative and wrongly overwrite dist[1]. Why this step? The explicit if dist[u] != inf check exists to stop that overflow bug.

Answer: dist = [0, 3, ∞].

Verify: $2$ has no incoming path from source, so it stays $\infty$; $1$'s only reachable route is the direct $3$. ✓

---

Ex 7 — Cell G: degenerate single vertex

Forecast: how many passes is $V-1$ here?

1. Init. dist = [0].
2. Settle passes: $V-1=0$ passes → the loop body never runs.
3. Extra pass: no edges → nothing relaxes → no cycle.

Answer: dist = [0].

Verify: The distance from a node to itself is $0$; with no edges nothing else exists. The $V-1=0$ boundary correctly does zero work. ✓ This confirms the loop bound is inclusive-safe at the smallest input.

---

Ex 8 — Cell H: zero-weight cycle (the exact fence)

Forecast: a $0$-cost loop is neither profit nor loss. Should the detector fire?

1. Init. dist = [0, ∞, ∞]. $V=3$ → 2 settle passes.
2. Pass 1. $0\to 1$: dist[1]=2. $1\to 2$: $2-2=0$ → dist[2]=0. $2\to 1$: $0+2=2$, and $2<2$ is false → no change.
3. Pass 2. No edge improves.
4. Extra pass. $2\to 1$: $0+2=2<2$? No. Nothing relaxes → no cycle reported.

Answer: dist = [0, 2, 0], no cycle flag.

Verify: A $0$-weight loop leaves distances unchanged after one lap, so dist[u]+w < dist[v] is never strictly satisfied. Bellman-Ford flags strictly negative cycles only — the strict < is exactly what keeps the fence-case silent. ✓

---

Ex 9 — Cell I: real-world word problem

Forecast: which is better, $A\to C$ (rate $5$) or $A\to B\to C$ (rate $2\times 3=6$)? The bigger product = the more negative summed toll.

1. Model. Turn "multiply rates" into "add tolls" via $w=-\ln (\text{rate})$. Why this step? Bellman-Ford adds weights; logarithms turn products into sums, so a profitable path = a smallest (most negative) sum. A negative cycle here would mean arbitrage (free money looping trades).
2. Init. dist = [0, ∞, ∞] for $A,B,C$.
3. Relax. $A\to B$: dist[B] = -ln 2 ≈ -0.6931. $B\to C$: -ln2 - ln3 = -ln6 ≈ -1.7918. $A\to C$: -ln5 ≈ -1.6094. Since $-1.7918<-1.6094$, keep dist[C] = -ln6.
4. Extra pass. No cycle (edges only go forward) → no arbitrage.

Answer: best route $A\to B\to C$ with summed toll $-\ln 6\approx -1.7918$, i.e. rate $6$ (beats direct $5$).

Verify: $e^{1.7918}=6$ and $6>5$, so the two-hop trade genuinely yields more currency. The chosen path corresponds to the smallest weight, exactly what shortest-path minimises. ✓ (Arbitrage detection via negative cycles is a classic Bellman-Ford application — see Shortest Path Problem.)

---

Ex 10 — Cell J: exam twist "which pass first settles $v$?"

Forecast: with the worst possible order, information crawls one edge per pass — so guess a number near $V-1$.

1. Pass 1. Only $0\to 1$ can fire (all others start from $\infty$): dist[1]=1. Reach = 1 hop.
2. Pass 2. $1\to 2$ fires: dist[2]=2. Reach = 2 hops.
3. Pass 3. dist[3]=3. Pass 4. dist[4]=4. Why this step? With reversed order, each pass pushes the "frontier" exactly one edge forward, so vertex at depth $d$ settles on pass $d$.

Answer: dist[4]=4 first correct on pass 4 ($=V-1$, the worst case). Fewer passes would leave it $\infty$.

Verify: Longest shortest-path here has $4$ edges $=V-1$. The reversed order is the pathological one that actually needs all $V-1$ passes — proving the bound is tight, not loose. ✓

---

Recall Which cell trips you up?

Ex 4 vs Ex 5 — both contain a negative cycle. Why does only one get flagged? Only Ex 4's cycle is reachable from the source; Ex 5's cycle sits in an unreachable component so its vertices stay $\infty$ and its edges are never relaxed.

Ex 4 vs Ex 8 — both have a cycle. Why does only Ex 4 flag? Ex 4's cycle sums to $-1$ (strictly negative → relax fires forever); Ex 8's sums to $0$ (the strict < never triggers).

---

Recall checks

---

Connections

• Dijkstra's Algorithm — would fail Ex 2 by finalizing the wrong dist[2]
• Dynamic Programming — every pass = advancing $k$ (edges used) in the DP
• Floyd-Warshall — the all-pairs cousin, also survives negatives
• Shortest Path Problem · Negative Weight Cycles · Graph Relaxation · SPFA