FloydWarshall

Floyd-Warshall is an algorithm for finding shortest paths between all pairs of vertices in a weighted graph. It handles directed and undirected graphs and allows for negative edge weights, provided the graph does not contain any negative weight cycles.

The algorithm uses dynamic programming to iteratively improve estimates of the shortest path distances. It maintains a distance matrix dist, where dist[i][j] represents the current best known distance from vertex i to vertex j. Initially, dist[i][j] is the direct edge weight from i to j, with dist[i][i] set to zero and dist[i][j] set to infinity if no edge exists. The core update is dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all pairs (i, j) using each vertex k as an intermediate node. After considering all vertices as intermediates, dist[i][j] equals the shortest path distance from i to j, assuming no negative cycles.

In addition to distances, the algorithm can maintain a predecessor or next matrix to reconstruct actual paths between any pair of vertices. Negative cycles are detected by checking whether dist[i][i] becomes negative for any i after the computation.

The typical implementation runs in O(n^3) time and uses O(n^2) space, making it well-suited for dense graphs or scenarios where all-pairs shortest paths are required in a single run. It forms the boolean Warshall variant for transitive closure when edge weights are replaced with boolean reachability values. While it is less efficient than running Dijkstra's algorithm repeatedly on sparse graphs with nonnegative weights, Floyd-Warshall provides a straightforward and universal solution for static graphs where all-pairs information is needed.