The All-Pairs Problem

The all-pairs shortest path problem asks: what is the shortest distance between every pair of vertices in the graph?

If you have $n$ vertices, you need to compute $n^2$ distances. One approach is to run Dijkstra from each vertex, giving $O((n^2 + nm) \log n)$ time. Floyd-Warshall solves this in $O(n^3)$ time with simpler code and handles negative edges (as long as no negative cycles exist). For dense graphs or when you need all distances, Floyd-Warshall is the standard choice.

Space complexity is $O(n^2)$ for the data structures used.