AllPairsShortestPath

All-Pairs Shortest Path (APSP) is the problem of finding the minimum-distance paths between every pair of vertices in a weighted graph. Given a directed or undirected graph G=(V,E) with edge weights w, the objective is to compute the matrix D where D[u,v] is the length of the shortest path from u to v. If no path exists, D[u,v] is typically infinity. In addition to distances, a corresponding predecessor or next-hop matrix can be produced to reconstruct the paths.

Floyd-Warshall is the canonical solution for dense graphs. It uses dynamic programming to allow intermediate vertices one by one, computing shortest distances in a triple-nested loop. The algorithm runs in O(n^3) time and O(n^2) space. It supports negative edge weights but requires that there be no negative-weight cycles; the presence of such a cycle makes some distances undefined, and the algorithm can detect this condition by inspecting the diagonal of the distance matrix after completion.

For sparse graphs, Johnson's algorithm is common: reweight edges to remove negatives, then run Dijkstra from each vertex. This yields O(n m log n) time with a binary-heap priority queue and O(n^2) space for the final distances. If weights are nonnegative, running Dijkstra from every vertex is a practical alternative with the same asymptotic bound. In graphs with only unweighted edges, BFS from each vertex can compute all-pairs shortest paths in O(n(m+n)) time, effectively a transitive closure.

Output and variants: The main output is a distance matrix D, with optional next-hop or predecessor information to reconstruct paths. The APSP problem is foundational in network routing, geography and social-network analysis.