Overview
Floyd-Warshall all-pairs shortest path deta hai — har node se har dusre node tak shortest distance.
Analogy
Jaise har city se har dusri city ka fastest route nikaalna — ek saath sab nikaalo.
Step-by-step
- dist[i][j] = direct edge weight (infinity agar nahi)
- k = 0 se V-1 tak: intermediate node consider karo
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Negative cycle: dist[i][i] < 0
Visual
dist[i][j] = min(
dist[i][j], # direct path
dist[i][k]+dist[k][j] # via k
)
Common mistakes
- Self-distance dist[i][i] = 0 initially set karna
- Negative cycle: diagonal mein negative check karo
- Integer overflow — large/infinity values se
Practice questions
- Floyd-Warshall implement karo aur all-pairs shortest paths nikalo
- Transitive closure matrix nikalo Floyd-Warshall se