Core idea
Floyd-Warshall computes all-pairs shortest paths with dynamic programming.
The distance matrix starts with direct edge weights, zeroes on the diagonal, and infinity for unreachable pairs.
For each intermediate vertex k, it checks whether i -> k -> j improves the current distance from i to j.
How it works
- Initialize a V x V distance matrix from the weighted graph.
- Choose each vertex k as the allowed intermediate vertex.
- For every source i and destination j, compare dist[i][j] with dist[i][k] + dist[k][j].
- Update dist[i][j] when the route through k is shorter.
- After all k values are processed, the matrix stores shortest distances for every ordered pair.