All-Pairs Shortest Path

One type of the shortest path problem.

As noted in the single-source shortest path (SSSP) problem, all-pairs shortest path (APSP) problem is technically solvable by running the SSSP algorithm on every vertex.

However, there are more efficient algorithms to solve this problem using dynamic programming.

Common application of this problem is to find the maximum diameter of a graph (maximum shortest path between any two vertices).

Table of contents
  1. Problem Definition
  2. General Algorithm Structure
    1. Adjacency Matrix Representation
    2. Outputs
  3. Optimal Subproblem of Shortest Paths
    1. Repeated Squaring
  4. Floyd-Warshall Algorithm

Problem Definition

Again, just like any shortest path problems, we are given weighted, directed graph $G = (V, E)$ with no negative cycles.

If you’re not sure what I’m talking about go back to shortest path problems.

The all-pairs shortest path (ASSP) problem:

$\forall u, v \in V$, find all shortest paths from $u$ to $v$.

General Algorithm Structure

Many algorithms are based on dynamic programming.

Adjacency Matrix Representation

In this problem, the input graph is often represented as an adjacency matrix of weights.

This matrix $W \in \mathbb{R}^{n \times n}$ is defined as:

$$ w_{ij} = \begin{cases} 0 & \text{if } i = j \\[0.5em] w(i, j) & \text{if } (i, j) \in E \\[0.5em] \infty & \text{otherwise} \end{cases} $$

Do not confuse this matrix with the shortest path weight matrix. The weights here represent direct edge weights.

Outputs

The output will be two $\mathbb{R}^{n \times n}$ matrices:

  • The shortest path weight matrix $L$, where each element is the shortest distance from $i$ to $j$:

$$ l_{ij} = \delta(i,j) $$

  • The predecessor matrix $\Pi$, where each element is the immediate predecessor of $j$ in a shortest path from $i$ to $j$:

$$ \pi_{ij} = \begin{cases} \text{NIL} & \text{if } i = j \lor \nexists p(i,j) \\[0.5em] j.\pi & \text{in some shortest path from } i \text{ to } j \end{cases} $$

The actual shortest path will be found by recursively traversing back the predecessor matrix:

Pseudocode 
def shortest_path(P, i, j):
  if i == j:
    return [i]

  pred = P[i][j]  
  if pred == None:
    return None
  prevs = shortest_path(P, i, pred)

  if prevs == None:
    return None
  else:
    return prevs + [j]

Optimal Subproblem of Shortest Paths

Let $|V| = n$.

Let’s organize the things we know.

  • Shortest path is acyclic: there can be at most $n - 1$ edges
  • Subpaths of shortest paths are shortest paths

Let $l_{ij}^{(k)}$ be the shortest path weight from $i$ to $j$ using at most $k$ edges.

So technically the entries of final $L$ are $l_{ij}^{(n-1)}$.

At the base case, $k = 0$:

\[l_{ij}^{(0)} = \begin{cases} 0 & \text{if } i = j \\[0.5em] \infty & \text{otherwise} \end{cases}\]

Assuming we know $l_{ij}^{(k-1)}$, we can compute $l_{ij}^{(k)}$ by taking another edge or not.

Assuming we know $l_{ix}^{(k-1)}$ for some $x$, we can compute $l_{ij}^{(k)}$ by taking the edge $(x, j)$.

This idea is captured in the following formula:

\[\begin{align*} l_{ij}^{(k)} = \min_{1 \leq x \leq n} \left( l_{ix}^{(k-1)} + w_{xj} \right) \end{align*}\]

Kind of like matrix multiplication, but we are taking the minimum instead of summing, adding instead of multiplying.

Since $w_{jj} = 0$, the above formula captures all assumptions above.

It is not hard to see that finding all entries of $L^{(k)}$ will take $\Theta(n^4)$ time (nested loops for $k$, $i$, $j$, and $x$).

So we know that $L^{(k)}$ is determined by $L^{(k-1)}$ and $W$.

Let us denote the interaction between $L^{(k-1)}$ and $W$ as operator $\bullet$.

Interesting observation is that $L^{(0)}$ is actually an identity element under this operator:

\[L^{(0)} \cdot W = W\]

Then:

\[L^{(k)} = L^{(0)} \cdot W^{k} = W^{k}\]

Repeated Squaring

To find our desired final $L$ matrix (or $L^{(n-1)}$), we need to calculate $W^{n-1}$.

However, we don’t actually have to do this operation sequentially.

We can just square the operations until $k$ reaches $n-1$:

\[L^{(2^\lceil \log_2 n \rceil)} = W^{2^\lceil \log_2 n \rceil}\]

So our outer loop on $k$ is now $O(\log n)$ instead of $O(n)$.

This results in overall complexity of $O(n^3 \log n)$ instead of $O(n^4)$.

Might as well use Dijkstra’s algorithm for each vertex, which would give us same complexity. We want a better algorithm.

Floyd-Warshall Algorithm

  • Can handle negative weights, but not negative cycles of course
  • Dynamic programming
  • $O(n^3)$ time complexity
  • Reuse shortest paths for intermediate vertices