Floyd-Warshall Algorithm

overview

Summary

Floyd-Warshall computes shortest path distances between every pair of vertices in a weighted graph, even with negative edges. It uses dynamic programming over a distance matrix and iteratively improves paths using each node as an intermediate. The runtime is O(n^3) with O(n^2) space, which is practical for dense graphs or when you need many queries. It also detects negative cycles and can be adapted for path reconstruction and transitive closure.