Floyd-Warshall — all-pairs shortest paths, O(V³)

3.5.12 · Coding › Graphs

WHAT hai problem?

Output ek poora $V \times V$ distances ka matrix hota hai (aur optionally paths reconstruct karne ke liye ek aur matrix).

WHY ek naya algorithm (aur Dijkstra ko V baar run kyun nahi karte)?

Har source se Dijkstra run karo: $O (V \cdot (E + V lo g V))$ — lekin negative edges ke saath kaam nahi karta.
Har source se Bellman-Ford run karo: $O (V \cdot V E) = O (V^{2} E)$ , jo dense graphs ( $E \approx V^{2}$ ) ke liye $O (V^{4})$ ho jaata hai.
Floyd-Warshall: ek clean $O (V^{3})$ , negative edges handle karta hai, aur sirf 5 lines ka code hai. Dense graphs aur chhote $V$ (maano $V \leq 400$ ) ke liye yeh king hai.

HOW: scratch se derive karo (dynamic programming)

Ek subproblem ko carefully define karte hain — yahi iska dil hai.

Base case ( $k = 0$ ): koi intermediate vertex allowed nahi, toh sirf single edges hi valid paths hain. $d_{0} (i, j) = ⎩ ⎨ ⎧ 0 w (i, j) + \infty i = j (i, j) \in E otherwise$

Transition — key insight. $i$ se $j$ tak ke shortest path ko consider karo jo intermediates ${1, \dots, k}$ use karta hai. Vertex $k$ ya toh is path mein use hota hai ya nahi:

$k$ USE nahi hota → path sirf ${1, \dots, k - 1}$ use karta hai, toh uski length $d_{k - 1} (i, j)$ hai.
$k$ USE hota hai → kyunki koi negative cycle nahi hai, optimal path $k$ ko exactly ek baar visit karta hai. Isse $k$ par split karo: ek piece $i \to k$ aur ek piece $k \to j$ , dono sirf ${1, \dots, k - 1}$ ko intermediates ke roop mein use karte hain. Toh uski length $d_{k - 1} (i, k) + d_{k - 1} (k, j)$ hai.

Hum dono mein se better lete hain:

2D array mein collapse karna (in-place trick)

Recurrence layer $k$ ko layer $k - 1$ se update karta hai. Hum same matrix $d$ ko overwrite kar sakte hain. Kya yeh safe hai? Jab $d [i] [j]$ compute karte hain $d [i] [k] + d [k] [j]$ use karke:

$d [i] [k]$ nayi layer mein = $min (d [i] [k], d [i] [k] + d [k] [k])$ . Kyunki $d [k] [k] = 0$ hai (koi negative cycle nahi), yeh unchanged rehta hai.
Same $d [k] [j]$ ke liye bhi.

Toh overwriting un values ko corrupt nahi karta jo hum read karte hain. Isliye ek $V \times V$ matrix kaafi hai.

def floyd_warshall(n, dist):       # dist[i][j] = weight or INF, dist[i][i]=0
    for k in range(n):             # k = intermediate vertex being "unlocked"
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Negative cycles detect karna

Run karne ke baad, diagonal check karo. Agar koi $d (i, i) < 0$ hai, toh $i$ ek negative cycle par hai (aapne $i$ se $i$ tak wapas jaane ka ek aisa path paaya jo rukne se bhi sasta hai).

Ek next[i][j] (ya parent[i][j]) matrix rakho. Har edge ke liye next[i][j] = j initialize karo. Jab bhi $k$ se relax karo, next[i][j] = next[i][k] set karo. $i \to j$ rebuild karne ke liye: next follow karo jab tak $j$ nahi milta.

Figure — Floyd-Warshall — all-pairs shortest paths, O(V³)

Worked Example 1 — ek chhota 3-node graph

Vertices $0, 1, 2$ . Edges: $0 \to 1 = 4$ , $0 \to 2 = 11$ , $1 \to 2 = 2$ . Koi aur nahi.

Initial matrix ( $\infty$ ko $\cdot$ dikhaya hai):

from\to	0	1	2
0	0	4	11
1	·	0	2
2	·	·	0

Unlock $k = 0$ : koi path 0 se guzar ke improve hota hai? Koi bhi 0 mein point nahi karta, toh koi change nahi. Yeh step kyun? $d [i] [0] = \infty$ hai $i \neq = 0$ ke liye, toh $d [i] [0] + d [0] [j]$ bahut bada hai.

Unlock $k = 1$ : $d [0] [2]$ vs $d [0] [1] + d [1] [2] = 4 + 2 = 6 < 11$ check karo. $d [0] [2] = 6$ update karo. Yeh step kyun? Ab route $0 \to 1 \to 2$ legal hai kyunki 1 unlock ho gaya hai.

Unlock $k = 2$ : 2 ke koi outgoing edges nahi hain, koi improvement nahi.

Final $d [0] [2] = 6$ . ✔

Worked Example 2 — negative edge (jahan Dijkstra fail hota hai)

Vertices $0, 1, 2$ . Edges: $0 \to 1 = 4$ , $0 \to 2 = 5$ , $1 \to 2 = - 3$ .

Initial: $d [0] [1] = 4, d [0] [2] = 5, d [1] [2] = - 3$ .

$k = 1$ : $d [0] [2]$ vs $d [0] [1] + d [1] [2] = 4 + (- 3) = 1 < 5$ → $d [0] [2] = 1$ update karo. Yeh step kyun? Negative edge $1 \to 2$ 1 se guzarne wale detour ko sasta banata hai — Floyd-Warshall isse naturally handle karta hai kyunki min edge sign ki parwah nahi karta (jab tak koi negative cycle nahi hai).

Final $d [0] [2] = 1$ . Dijkstra galati se $5$ commit kar deta.

Worked Example 3 — negative cycle detection

Edges: $0 \to 1 = 1, 1 \to 2 = - 1, 2 \to 0 = - 1$ . Cycle total $= 1 - 1 - 1 = - 1 < 0$ .

Run karne ke baad, $d [0] [0]$ relax hokar $1 + (- 1) + (- 1) = - 1 < 0$ ho jaata hai. Diagonal negative ho jaata hai → negative cycle detect ho gaya. Yeh step kyun? Diagonal $d [i] [i]$ 0 se start hota hai; sirf ek negative loop back to $i$ isse 0 se neeche le ja sakta hai.

Recall Feynman: 12-saal ke bachche ko explain karo

Socho cities raston se judi hain jinke travel times hain. Aapko har pair of cities ke beech fastest time chahiye. Aap ek game khelte ho: "Agar mujhe ab raaste mein City A par rukne ki permission ho toh?" Aap har pair ko recheck karte ho: shayad A se jaana faster ho. Phir City B bhi unlock karo, sabko phir recheck karo. Phir City C... Jab aap saari cities unlock kar lete ho, tab har pair ke paas already uska fastest time hota hai. Bas itna hi — aapne sirf baar-baar poochha "kya is nayi city par rukne se madad milegi?" ek-ek city ke liye.

Active Recall

Floyd-Warshall mein DP state

d_{k} (i, j)

kya represent karta hai?

i

j

tak ka shortest path sirf

{1, \dots, k}

vertices ko intermediates use karte hue (endpoints hamesha allowed).

Floyd-Warshall recurrence kya hai?

d_{k} (i, j) = min (d_{k - 1} (i, j), d_{k - 1} (i, k) + d_{k - 1} (k, j))

Floyd-Warshall ki time aur space complexity kya hai?

O (V^{3})

time,

O (V^{2})

space.

k

loop outermost kyun hona chahiye?

k

par recurse karta hai; saare pairs ko

{1, \dots, k}

account karna finish karna hoga

k + 1

unlock karne se pehle, warna aap half-updated values read karte ho.

Floyd-Warshall se negative cycle kaise detect karte hain?

Run karne ke baad, agar koi

d (i, i) < 0

hai toh

i

ek negative cycle par hai.

Kya Floyd-Warshall negative edge weights handle kar sakta hai?

Haan, jab tak koi negative cycle nahi hai. (Dijkstra negative edges handle nahi kar sakta.)

In-place single-matrix update correct kyun hai?

d [i] [k]

aur

d [k] [j]

read karna safe hai kyunki

d [k] [k] = 0

matlab woh entries iteration

k

mein change nahi hoti.

Base case (

k = 0

) matrix kya hota hai?

Diagonal par

0

, edge weight

w (i, j)

agar edge exist karta hai, warna

+ \infty

Floyd-Warshall mein paths kaise reconstruct karte hain?

next[i][j] rakho; edges ke liye

j

se init karo;

k

se relaxation par next[i][j]=next[i][k] set karo; rebuild ke liye next follow karo.

Dijkstra ko V baar run karne se Floyd-Warshall kab better hai?

Dense graphs, chhota

V

, ya negative edges wale graphs mein; clean

O (V^{3})

vs dense ke liye

O (V^{2} E)

se behtar.

Connections

Dijkstra's Algorithm — single-source, sirf non-negative weights
Bellman-Ford — single-source, negatives handle karta hai, negative cycles detect karta hai
Dynamic Programming — Floyd-Warshall intermediate sets par layered DP hai
Johnson's Algorithm — sparse graphs ke liye APSP, reweight karta hai phir Dijkstra run karta hai
Transitive Closure — same loop structure min ki jagah OR ke saath (Warshall's algorithm)
Negative Cycles — diagonal se detection