Overview
Floyd-Warshall all-pairs shortest paths ka dynamic programming algorithm hai, negative weights handle karta hai.
Analogy
Jaise saare cities ke beech shortest distance table banana—sab intermediate cities ki routes mein shortest dhundo.
Step-by-step
- V×V distance matrix initialize karo (same=0, edge=weight, warna=∞)
- Har intermediate node k par loop karo
- dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
- Diagonal negative hai toh negative cycle
Visual
V=4
for k in range(4):
for i in range(4):
for j in range(4):
d[i][j]=min(d[i][j],d[i][k]+d[k][j])
Common mistakes
- Negative cycle detection skip karna (diagonal check karo)
- Triple loop order galat likhna
Practice questions
- Matrix graph par Floyd-Warshall implement karo
- Floyd-Warshall se negative cycle hai ya nahi check karo