Visual walkthrough — Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE)

We assume nothing. If you have never seen a graph, a distance array, or the word "relax", start reading at line one — every symbol is earned before it is used.

---

Step 1 — What is the thing we are trying to compute?

WHAT. We have a set of cities (called vertices, drawn as dots) and one-way roads between them (called edges, drawn as arrows). Each road has a number written on it — the weight — the cost of driving down that road. A weight can be negative, meaning that road pays you money to drive it.

We pick one city as home, called the source and written $s$. Our goal:

WHY define it this way. "Smallest total weight" is just adding up every road's number along a route. Because some numbers can be negative, a longer route (more roads) might cost less. That single fact is what makes this hard — and is why the greedy Dijkstra's Algorithm cannot be trusted here.

PICTURE. Look at the four dots and their arrows. Green numbers are positive tolls; the magenta arrow $1\to 2$ has weight $-3$ — a road that pays you.

• $s=0$ is the home dot (violet).
• Each arrow's label is its weight $w(u,v)$: the symbol $w$ is a function — feed it a road $(u,v)$, it returns that road's number.

---

Step 2 — A distance array: our only memory

WHAT. We keep one list of numbers, one slot per vertex, called dist. The slot dist[v] holds the best route cost to $v$ that we know about so far — not necessarily the true answer yet, just our current best guess.

WHY. We refuse to be clever. We will only ever improve guesses, never finalize them early. That humility is the whole reason Bellman-Ford survives negative edges.

We start every guess as "impossibly far": $\text{dist}[s]=0,\text{dist}[v]=\infty (v\ne s)$

• $\text{dist}[s]=0$: it costs nothing to already be home.
• $\infty$ (the sideways-8, "infinity") means "no route found yet". It is a placeholder for unreachable-so-far, guaranteed to be beaten by any real number.

PICTURE. The array as four boxes. Home is $0$; everyone else is $\infty$.

---

Step 3 — One move: relaxation

WHAT. Pick any road $u\to v$ with weight $w$. Ask one question:

"If I travel to $u$ for dist[u], then take this road for $w$, is that cheaper than my current guess dist[v]?"

If yes, overwrite the guess. In code:

$\text{relax}(u,v,w):\text{if }\text{dist}[u]+w<\text{dist}[v]\text{ then }\text{dist}[v]\leftarrow \text{dist}[u]+w$

Term by term, at the exact spot each appears:

• $\text{dist}[u]$ — cost to reach the start of the road.
• $+w$ — add the road's own toll.
• $<\text{dist}[v]$ — compare against the current best guess at the destination.
• $\leftarrow$ — the arrow means "store into"; we only store when it's an improvement.

WHY this operation and not another? Relaxation is the only way a route can get better: any cheaper route to $v$ must end on some final road $u\to v$, and its cost is exactly "(cost to $u$) + (that road)". So checking every road covers every possible improvement. This is the atom of Graph Relaxation.

PICTURE. Before: dist[2]=5. We relax $1\to 2$ with $w=-3$ while dist[1]=4. Since $4+(-3)=1<5$, the guess drops to $1$.

---

Step 4 — One pass: relax every road once

WHAT. A pass means: go through the entire list of edges and relax each one, in some fixed order.

WHY. A single relax only improves one destination. A whole pass gives every road one chance to hand its improvement forward. Doing this repeatedly lets good news travel across the graph like a wave.

PICTURE — the wave after pass 1. Start from all-$\infty$ (except home). Following the edge order $0\to 1,0\to 2,1\to 2,2\to 3$:

• $0\to 1$: $0+4=4<\infty$, so dist[1]=4.
• $0\to 2$: $0+5=5<\infty$, so dist[2]=5.
• $1\to 2$: $4+(-3)=1<5$ ✅ — the negative road beats the direct one. dist[2]=1.
• $2\to 3$: uses the fresh $1$ → $1+2=3$, so dist[3]=3.

Notice: because $1\to 2$ was relaxed before $2\to 3$ in this order, the improvement rippled two hops in a single pass. Order changes how far the wave travels per pass — but never the final answer.

---

Step 5 — Why the wave is a dynamic program in disguise

WHAT. Define a two-index table: $D[k][v]=\text{best cost to }v\text{ using a route of }\text{at most }k\text{ edges.}$

• $k$ = a budget on how many roads the route may use.
• $v$ = which vertex we're pricing.

The rule that builds row $k$ from row $k-1$: $D[k][v]=\min (\underset{\text{use no new edge}}{\underbrace{D[k-1][v]}},\underset{\text{arrive via one final edge }u\to v}{\underbrace{\underset{(u,v)\in E}{\min }(D[k-1][u]+w(u,v))}})$

Reading it aloud: the cheapest route to $v$ within budget $k$ is either a route we already had within budget $k-1$, or a within-$(k-1)$ route to some neighbour $u$ plus one last road $u\to v$. There is no third possibility — a route either uses that extra edge budget or it doesn't. This is the Dynamic Programming heart of the algorithm.

WHY it matches Step 4. Compare the $\min (D[k-1][u]+w)$ term with the relaxation test $\text{dist}[u]+w<\text{dist}[v]$. They are the same arithmetic. So one pass over all edges advances the budget $k$ by at least one. The dist[] array is just the current row of this table with the old rows thrown away (we never need them).

PICTURE. The table stacked as rows; each pass fills the next row downward; each cell points back to the min of two candidate arrows.

---

Step 6 — Why we stop at exactly $V-1$ passes

WHAT. We claim: after $V-1$ passes the guesses are the true answers, where $V$ = number of vertices.

WHY. Suppose there is no negative cycle. Then the true shortest route to any $v$ never revisits a vertex — because looping back would only add non-negative weight, so a repeat is never helpful. A route that visits each vertex at most once touches at most $V$ vertices, and $V$ vertices are joined by at most $V-1$ roads.

So every true shortest path fits inside a budget of $V-1$ edges — meaning row $D[V-1]$ already contains the final answers: $\text{dist}(v)=D[V-1][v]$

PICTURE. A path threading all $V=4$ dots uses exactly $3=V-1$ arrows. Add a repeated dot and you've made a cycle, not a simple path.

---

Step 7 — The degenerate case: a negative cycle

WHAT. A negative cycle is a loop of roads whose weights sum to a negative number. Drive it once, you're richer; drive it forever, your "distance" falls without bound. There is then no finite shortest path to anything the loop can reach.

WHY one extra pass exposes it. After $V-1$ passes, everything that could settle has settled (Step 6). So run one more pass. If any edge can still be relaxed, the improvement cannot come from a longer simple path (those maxed out at $V-1$ edges) — the only remaining explanation is a cycle that keeps paying you. See Negative Weight Cycles.

$\text{After pass }V-1:\text{any }\text{dist}[u]+w<\text{dist}[v]\Rightarrow \text{negative cycle reachable from }s$

PICTURE. The triangle $0\to 1\to 2\to 0$ with weights $1,-1,-1$ sums to $-1$. Each lap drops all three guesses by $1$; the numbers never converge.

---

Step 8 — Two full worked traces

Example A (normal, with a negative edge). Graph of Step 1, source $0$:

pass	dist[0]	dist[1]	dist[2]	dist[3]
init	0	∞	∞	∞
1	0	4	1	3
2	0	4	1	3

Pass 2 changed nothing → the early-exit trick fires and we stop before $V-1=3$ passes. The extra detection pass also changes nothing → no negative cycle. Answer: $[0,4,1,3]$.

Example B (negative cycle). Edges $0\to 1(1),1\to 2(-1),2\to 0(-1)$, source $0$. Loop weight $=1-1-1=-1<0$. After $V-1=2$ passes the distances are still dropping; the extra pass still relaxes an edge → we return a negative-cycle flag, not numbers (the numbers would be meaningless).

PICTURE. Both traces side by side: A converges and flattens; B keeps sliding downhill.

---

The one-picture summary

Everything above compressed into a single flow: init → $V-1$ relaxing passes (the wave) → one reacting pass (the detector).

Recall Feynman retelling — the whole walkthrough in plain words

You start at home with cost $0$ and mark every other city as "unknown" ($\infty$). A relax is one tiny question about one road: "reach the start of this road, add its toll — cheaper than what I had at the end?" If yes, write the smaller number. A pass asks that question for every road once, so good news ripples one or more hops outward like a wave. Because a route that never repeats a city can use at most (cities $-1$) roads, doing (cities $-1$) full passes lets the wave reach as far as it ever needs to — the numbers are now final. Then you do one more pass just to listen: if any road still wants to lower a number, there's no honest reason left except a loop that pays you every lap — a negative cycle — so you raise a flag instead of reporting nonsense numbers. "V minus one to relax, one more to react."

---

Connections

• 3.5.11 Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE) (Hinglish)
• Dijkstra's Algorithm — the greedy method the negative edges break
• Dynamic Programming — the $D[k][v]$ table is the real engine
• Floyd-Warshall — all-pairs cousin, also negative-safe
• Shortest Path Problem
• Negative Weight Cycles
• Graph Relaxation
• SPFA — queue-based speedup of the same ripple