Floyd-Warshall computes shortest paths between all pairs of vertices in O(V³) time and O(V²) space using dynamic programming. It iterates through intermediate vertices k, updating distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]). Unlike Dijkstra, it handles negative-weight edges (but not negative cycles) and is simple to implement.
Trace the algorithm on a small graph, layer-by-layer through intermediate vertices k. Understand the recurrence relation and why the triple-nested loop works. Detect negative cycles by checking the diagonal. Compare to running Dijkstra V times.
You know Dijkstra's algorithm finds the shortest path from one source to all other vertices. But what if you need the shortest path between *every* pair of vertices — not just from one source, but from all of them? You could run Dijkstra V times (once from each vertex), but the Floyd-Warshall algorithm offers an elegant alternative built on dynamic programming, which you have already studied.
The algorithm maintains a V×V matrix `dist[i][j]` representing the best known distance from vertex i to vertex j. Initially, `dist[i][j]` is the weight of the direct edge from i to j (or infinity if no edge exists), and `dist[i][i]` is 0. Then comes the key insight: Floyd-Warshall iterates through every vertex k as a potential intermediate vertex and asks a simple question for every pair (i, j): "Is it shorter to go from i to j through k?" If `dist[i][k] + dist[k][j] < dist[i][j]`, then yes — update the distance. After considering all V possible intermediate vertices, the matrix contains the shortest path between every pair.
The recurrence relation makes this precise: `dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j])`, where the subscript k means "using only vertices 1 through k as intermediates." This is classic dynamic programming — building the solution by expanding the set of allowed intermediate vertices one at a time. The implementation is famously compact: three nested loops (for k, then i, then j), a single comparison, and a conditional update. The order of the loops matters — k must be the outermost loop — because each layer builds on the previous one.
A major advantage over Dijkstra is that Floyd-Warshall handles negative-weight edges correctly. Dijkstra's greedy strategy breaks when edges can be negative, but Floyd-Warshall's exhaustive dynamic programming approach works fine — it simply tries all intermediate paths and keeps the minimum. The one thing it cannot handle is negative-weight cycles (a cycle whose edge weights sum to a negative number), because you could traverse such a cycle infinitely to reduce the path length without bound. You can detect negative cycles by checking the diagonal of the result matrix: if any `dist[i][i] < 0`, vertex i is part of a negative cycle. The algorithm runs in O(V³) time and O(V²) space regardless of the number of edges, which makes it ideal for dense graphs but potentially wasteful for sparse ones where running Dijkstra from each vertex (with a priority queue) would be faster.