liveBook · Manning

All-pairs shortest path

As explained in Algorithms Every Programmer Should Know

The problem of finding the minimum path cost between every pair of vertices in a graph.

The all-pairs shortest path (APSP) problem asks for the minimum path cost between every pair of vertices in a weighted graph. Floyd–Warshall solves it in one run, building a global distance matrix rather than searching outward from one starting vertex at a time. section 9.0 section 9.4

For each possible intermediate vertex k, compare the known cost from i to j with the cost of going from i to k and then k to j. Keep the cheaper value; after testing every bridge, the matrix stores the shortest distance for every pair. Initialize direct edges with their weights, self-distances with zero, and missing connections with infinity. section 9.1 section 9.4

A bridge creates a shorter route

In the four-node walkthrough, testing node 1 as a bridge changes the distance from node 4 to node 2 from infinity to 4, using edges with costs 2 and 2. Later phases test the remaining nodes and complete the distance matrix. section 9.1

Figure 9.1 The initial state of the network. The left panel shows the directed, weighted graph. The right panel shows the baseline distance matrix (A0). Existing direct paths are recorded with their cost, while missing connections are initialized to infinity (∞). The diagonal is zero, as the distance from any node to itself is zero.

Use the initial graph and distance matrix to see how direct edges, unreachable pairs, and self-distances are represented before the updates begin. section 9.1

The method takes O(V³) time and O(V²) space, and can update its matrix in place. It trades upfront computation for constant-time distance lookups afterward. It supports negative edge weights and can detect a negative cycle when a final diagonal entry is negative; repeated single-source searches are more efficient on sparse graphs. section 9.1 section 9.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through matrix initialization, bridge-by-bridge updates, complexity, and negative-cycle detection.
Examples
Traces a four-node weighted graph as bridge vertices improve entries in its distance matrix.
What it assumes
Uses weighted graphs and a distance matrix, while introducing how to initialize that matrix from direct edges.
What you can do after
Apply it via Python to compute a distance matrix and identify negative cycles from negative diagonal entries.
How it connects
Connects APSP to dynamic programming, Floyd–Warshall, and Dijkstra’s algorithm.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.