Introduction to All-Pairs Shortest Paths

Shortest path tree

Previously, we discussed several algorithms to find the shortest paths from a single source vertex $s$ to every other vertex of the graph by constructing the shortest path tree rooted at $s$. The shortest path tree specifies two pieces of information for each node $v$ in the graph:

• $dist(v)$ is the length of the shortest path from $s$ to $v$.
• $pred(v)$ is the second-to-last vertex in the shortest path from $s$ to $v$.

Now, we consider the more general all-pairs shortest path problem, which asks for the shortest path from every possible source to every possible destination. For every pair of vertices $u$ and $v$, we want to compute the following information:

• $dist(u, v)$ is the length of the shortest path from $u$ to $v$.
• $pred(u, v)$ is the second-to-last vertex on the shortest path from $u$ to $v$.

These intuitive definitions exclude a few boundary cases, all of which we’ve already seen previously.

• If there is no path from $u$ to $v$, then there is no shortest path from $u$ to $v$; in this case, we define $dist(u, v) = ∞$

...