AllPairsPfade

AllPairsPfade is a term used in graph theory to denote a class of algorithms and data structures designed to compute, for every pair of vertices in a weighted graph, the shortest path between them and often the exact path itself. The typical problem setup involves a directed or undirected graph G = (V, E) with a weight function w on the edges, where the goal is to determine, for all pairs (u, v), both the distance from u to v and a concrete path that realizes that distance.

In its most common form, AllPairsPfade produces a distance matrix D where D[u][v] equals the length of a shortest path from u to v, together with a structure that enables path reconstruction. The Floyd-Warshall algorithm is the classic approach for dense graphs, providing D in O(n^3) time and enabling path retrieval via a successor or predecessor matrix. For sparse graphs, Johnson’s algorithm or repeated single-source shortest path runs (using Dijkstra with nonnegative weights or Bellman-Ford when negative weights are present) yield all-pairs information with better performance on certain inputs, typically around O(n m log n) for graphs with m edges.

Path reconstruction is a key feature of AllPairsPfade, often implemented via a next-hop or predecessor matrix that allows one to extract an explicit path from any source to any destination. Variants may include counting the number of shortest paths, enumerating all shortest paths, or supporting dynamic updates to respond to graph changes.

Applications span network routing, transportation planning, and analysis of global connectivity, where knowledge of all-pairs routes informs optimization, resilience, and feasibility assessments. See also All-Pairs Shortest Path, Floyd-Warshall, and Johnson’s algorithm.