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

3.5.11 · Coding › Graphs

Bellman-Ford HAI KYA?

KYUN chahiye yeh (jab Dijkstra exist karta hai)? Dijkstra assume karta hai ki ek baar koi node "finalize" ho jaaye, toh koi future path usse beat nahi kar sakta — yeh tabhi sach hai jab saare edges $\geq 0$ hon. Ek negative edge ek zyada hops wale path ko baad mein sasta bana sakta hai, jo Dijkstra ki greedy promise tod deta hai. Bellman-Ford koi greedy commitment nahi karta; woh bas tab tak relax karta rehta hai jab tak kuch improve nahi hota.

KAISE: DP derivation scratch se

Chaliye ise derive karte hain, memorize nahi.

Subproblem define karo: $D [k] [v] = shortest distance from source s to v using at most k edges.$

Base case (KYUN): $0$ edges ke saath aap sirf $s$ par reh sakte ho. $D [0] [s] = 0, D [0] [v] = \infty (v \neq = s)$

Transition (KYUN): $v$ tak ka ek path jo $\leq k$ edges use karta hai, ya toh:

$\leq k - 1$ edges use karta hai (kuch add nahi), ya
kisi neighbor $u$ tak $\leq k - 1$ edges mein path leta hai, phir edge $(u, v)$ .

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

$k = V - 1$ par KYUN rukein? Ek shortest path jisme koi negative cycle nahi hai woh simple hota hai (koi repeated vertex nahi), toh usmein at most $V$ vertices aur isliye at most $V - 1$ edges hote hain. Toh $D [V - 1] [v]$ hi sahi answer hai.

Relaxation = transition disguise mein

Humein 2D table ki zaroorat nahi hai. Ek array dist[] rakho aur "relax" karo:

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

Saare edges par ek full pass chalana = $k$ ko (kam se kam) ek se badhana. $V - 1$ passes karna convergence guarantee karta hai.

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

KAISE: negative cycle detection

Pseudocode (pura)

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

dist[u] != inf guard KYUN? inf + w phir bhi inf hi hai; guard ke bina aap kabhi galat relax nahi karte, lekin yeh spurious updates aur fixed-width integers wali languages mein overflow avoid karta hai.

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$ .

pass	dist[1]	dist[2]	dist[3]
init	∞	∞	∞
1	4	1 (via 1→2, $4 - 3$ )	3
2	4	1	3

Pass 1 mein dist[2]=1 kyun mila, 5 nahi? Order matter karta hai: humne pehle $0 \to 1$ relax kiya (dist[1]=4), phir $1 \to 2$ ne use kiya → $4 - 3 = 1$ , jo direct $5$ se better hai.
Pass 2 mein kuch KYUN nahi badla? Pehle se converge ho chuka hai; early-exit break trigger ho jaata hai. $V - 1 = 3$ saare passes ki zaroorat nahi thi.

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 \to 1 \to 2 \to 0$ ka weight $1 - 1 - 1 = - 1 < 0$ hai.

$V - 1 = 2$ passes ke baad, dist girti rehti hai.
Detection KYUN fire hoti hai: extra pass phir bhi koi edge relax karta hai (jaise $2 \to 0$ dist[0] improve karta hai). → negative cycle report karo.

Yeh step KYUN important hai: yahaan distances meaningless hain, isliye humein numbers nahi, ek flag return karna chahiye.

Common mistakes

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho cities ke beech travel karne ki prices hain, jahaan kuch roads tumhe paisa deti hain (negative cost). Tum ghar se har city tak ka sabse sasta rasta chahte ho. Tum "abhi tak ka sabse sasta jaana cost" ko update karte rehte ho, baar baar har road check karke. Poora map (cities ki sankhya − 1) baar check karne ke baad, prices girna band ho jaati hain — yahi tumhara answer hai. Lekin agar ek loop of roads hai jo har chakkar net paisa deti hai, toh tumhari cost kabhi girna band nahi hoti (free money forever!). Toh agar ek aur full check phir bhi koi price girata hai, tum chillate ho "ek money-loop hai!" — woh ek negative cycle hai.

Recall checks

Flashcards

Bellman-Ford time complexity

O (V \cdot E)

Bellman-Ford DP subproblem

D [k] [v]

source se

v

tak at most

k

edges use karke shortest dist

Why relax

V - 1

times

ek simple shortest path mein at most

V - 1

edges hote hain

Bellman-Ford transition

D [k] [v] = min (D [k - 1] [v], min_{(u, v)} D [k - 1] [u] + w (u, v))

How to detect a negative cycle

V - 1

passes ke baad, ek aur pass karo; agar koi edge phir bhi relax ho → negative cycle

Which negative cycles does it detect

sirf woh jo source se reachable hain

Why Dijkstra fails with negative edges

greedy finalization assume karta hai ki koi future sasta longer-hop path nahi hai; negative edges woh tod dete hain

Base case of Bellman-Ford DP

D [0] [s] = 0

D [0] [v] = \infty

for

v \neq = s

Early-exit optimization

agar ek pass mein koi update nahi hoti, ruk jao — distances pehle se converge ho chuke hain

Trick to detect ALL negative cycles

ek virtual source add karo jisme saare vertices par 0-weight edges hon

Connections

Dijkstra's Algorithm — tez ( $O (E lo g V)$ ) lekin non-negative edges chahiye
Dynamic Programming — Bellman-Ford "edges used" par DP hai
Floyd-Warshall — all-pairs version, negatives bhi handle karta hai, $O (V^{3})$
Shortest Path Problem
Negative Weight Cycles
Graph Relaxation
SPFA — Bellman-Ford ka queue-based optimization