45. All-Pairs Shortest Path: Introduction to Floyd-Warshall

Sometimes, we don't just need the shortest path from one source, but the shortest path between every pair of vertices. This is the All-Pairs Shortest Path problem.

Floyd-Warshall Algorithm

Floyd-Warshall is a classic algorithm that uses Dynamic Programming (covered soon) to solve this problem efficiently.

Concept

It considers every possible vertex k as an intermediate node for paths between two other nodes i and j.

For every pair of vertices (i, j), it checks if going through an intermediate vertex k is shorter than the current known shortest path.

python for k in range(V): for i in range(V): for j in range(V): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

• Time Complexity: O(V³). It is efficient when V is relatively small (hundreds), but less so for massive graphs.