A shortest path connects two vertices with the smallest total edge weight among possible routes. For all-pairs shortest paths, Floyd–Warshall checks whether routing through each vertex lowers the distance between any pair, producing a global distance lookup table. section 9.0
Negative edges can be included when no cycle has a negative total weight. A negative-weight cycle makes a shortest path undefined because looping can reduce the route cost without limit; after Floyd–Warshall runs, a negative diagonal distance signals such a cycle. section 9.3
Floyd–Warshall suits dense graphs when exact distances between every pair are needed. Its work is O(V³) regardless of edge count, so repeatedly running a single-source algorithm is more efficient for sparse graphs. section 9.3






