Floyd–Warshall algorithm

Summary

The Floyd–Warshall algorithm computes the shortest path lengths between all pairs of vertices of a weighted directed graph. It is a dynamic programming method that allows the vertices $1, \dots, k$ as intermediate stops, one more at each stage. It accepts negative edge weights as long as there is no negative cycle, and it runs in time $O(n^3)$ on $n$ vertices.