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

WHAT is Bellman-Ford?

WHY do we need it (when Dijkstra exists)? Dijkstra assumes once you "finalize" a node, no future path can beat it — true only if all edges are $\ge 0$. A negative edge can make a longer-hop path cheaper later, breaking Dijkstra's greedy promise. Bellman-Ford makes no greedy commitment; it just keeps relaxing until nothing improves.

HOW: the DP derivation from scratch

Let me derive it, not memorize it.

Define the subproblem: $D[k][v] = \text{shortest distance from source } s \text{ to } v \text{ using at most } k \text{ edges.}$

Base case (WHY): with $0$ edges you can only stay at $s$. $D[0][s] = 0, \qquad D[0][v] = \infty \ \ (v \ne s)$

Transition (WHY): a path to $v$ using $\le k$ edges either:

• uses $\le k-1$ edges (don't add anything), or
• takes a path to some neighbor $u$ in $\le k-1$ edges, then the edge $(u,v)$.

$D[k][v] = \min\Big(D[k-1][v],\ \min_{(u,v)\in E}\big(D[k-1][u] + w(u,v)\big)\Big)$

WHY stop at $k = V-1$? A shortest path with no negative cycle is simple (no repeated vertex), so it has at most $V$ vertices and hence at most $V-1$ edges. So $D[V-1][v]$ is the true answer.

Relaxation = the transition in disguise

We don't need the 2D table. Keep one array dist[] and "relax":

relax(u, v, w):  if dist[u] + w < dist[v]:  dist[v] = dist[u] + w

Running one full pass over all edges = advancing $k$ by (at least) one. Doing $V-1$ passes guarantees convergence.

HOW: negative cycle detection

Pseudocode (full)

def bellman_ford(V, edges, src):
    dist = [float('inf')] * V
    dist[src] = 0
    # V-1 relaxation passes
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:           # early exit optimization
            break
    # one extra pass -> detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None           # negative cycle reachable
    return dist

Why the dist[u] != inf guard? inf + w is still inf; without the guard you'd never wrongly relax, but it avoids spurious updates and overflow in languages with fixed-width ints.

Worked Example 1 — normal graph with a negative edge

Vertices $0,1,2,3$; edges: $0\!\to\!1\,(4),\ 0\!\to\!2\,(5),\ 1\!\to\!2\,(-3),\ 2\!\to\!3\,(2)$. Source $=0$.

• Why does pass 1 give dist[2]=1 not 5? Order matters: we relaxed $0\to1$ first (dist[1]=4), then $1\to2$ used it → $4-3=1$, beating the direct $5$.
• Why does pass 2 change nothing? Already converged; the early-exit break triggers. $V-1=3$ passes weren't all needed.

Answer: $[0,4,1,3]$.

Worked Example 2 — negative cycle

Edges: $0\!\to\!1\,(1),\ 1\!\to\!2\,(-1),\ 2\!\to\!0\,(-1)$. Source $=0$.

Cycle $0\to1\to2\to0$ has weight $1-1-1=-1<0$.

• After $V-1=2$ passes, dist keeps dropping.
• Why detection fires: the extra pass still relaxes some edge (e.g. $2\to0$ improves dist[0]). → report negative cycle.

Why this step matters: distances are meaningless here, so we must return a flag, not numbers.

Common mistakes

Recall checks

Flashcards

Connections

• Dijkstra's Algorithm — faster ($O(E\log V)$) but needs non-negative edges
• Dynamic Programming — Bellman-Ford is DP over "edges used"
• Floyd-Warshall — all-pairs version, also handles negatives, $O(V^3)$
• Shortest Path Problem
• Negative Weight Cycles
• Graph Relaxation
• SPFA — queue-based optimization of Bellman-Ford

Concept Map

Hinglish (regional understanding)