Overview
All-pairs shortest paths using dynamic programming; handle negative weights but not negative cycles.
Analogy
Asking every possible intermediate city: 'Could I go A→C→B faster than A→B directly?'
Step-by-step
- Initialize dist[i][j] = edge weight or ∞ if no edge; dist[i][i]=0.
- For each intermediate k: for each (i,j): dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]).
- After V iterations over k, dist[i][j] is shortest for all pairs.
Visual
V=3: iterate k=0,1,2 — each pass checks one intermediate city for all pairs.
Common mistakes
- Loop order: k is outermost, then i, then j — not i,j,k.
- Negative cycle detection: dist[i][i] < 0 after the algorithm indicates a negative cycle.
Practice questions
- Detect negative cycles using Floyd-Warshall.
- Find the shortest path between every pair in a dense graph.
AI Wisdom