Floyd-Warshall Algorithm

By the end, you can

• Explain the all-pairs shortest-path problem and why Floyd-Warshall solves it in one pass.
• State and apply the DP recurrence `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`.
• Trace the algorithm phase by phase on a small graph and fill in the evolving distance matrix.
• Explain why k must be the outermost loop and articulate the phase invariant.
• Describe why in-place updates are safe during each phase.
• Distinguish between negative edge weights (allowed) and negative cycles (forbidden) and explain how to detect the latter.
• Describe how to extend the algorithm to reconstruct actual paths via a `next` matrix.
• Compare Floyd-Warshall, Dijkstra, and Johnson's algorithm and choose the right tool given graph density, edge signs, and whether all pairs or a single source is needed.