All-Pairs Shortest Path (APSP)

overview

Summary

All-Pairs Shortest Path (APSP) finds the minimum distance between every pair of vertices in a graph. Common solutions include Floyd-Warshall for dense graphs and negative edge support, repeated Dijkstra for sparse nonnegative graphs, and Johnson's algorithm for sparse graphs with some negative edges. The choice depends on graph density, edge weights, and whether negative cycles exist. Outputs are typically a distance matrix and optionally a predecessor matrix for path reconstruction.