All-Pairs Shortest Paths: Floyd-Warshall and Johnson's Algorithm

Dijkstra and Bellman-Ford both compute shortest paths from a single source. Some problems genuinely need shortest paths between every pair of vertices — a full pairwise distance matrix for a network of trading venues, or an all-pairs contagion-distance table across a settlement network. Running Dijkstra $|V|$ times (once per source) is one way to get there; this note derives a second, structurally different approach — Floyd-Warshall's matrix dynamic program — and then shows how Johnson's algorithm combines both ideas to get the best of each for sparse graphs.