Chapter 25: All-Pairs Shortest Paths

| < Day Day Up > |

# Chapter 25: All-Pairs Shortest Paths

## Overview

In this chapter, we consider the problem of finding shortest paths between all pairs of vertices in a graph. This problem might arise in making a table of distances between all pairs of cities for a road atlas. As in Chapter 24, we are given a weighted, directed graph G = (V, E) with a weight function w : E → R that maps edges to real-valued weights. We wish to find, for every pair of vertices u, v ∈ V , a shortest (least-weight) path from u to v, where the weight of a path is the sum of the weights of its constituent edges. We typically want the output in tabular form: the entry in u's row and v's column should be the weight of a shortest path from u to v.

We can solve an all-pairs shortest-paths problem by running a single-source shortest-paths algorithm |V| times, once for each vertex as the source. If all edge weights are nonnegative, we can use Dijkstra's algorithm. If we use the linear-array implementation of the min-priority queue, the running time is O(V3 + V E) = O(V3). The binary min-heap implementation of the min-priority queue yields a running time of O(V E lg V), which is an improvement if the graph is sparse. Alternatively, we can implement the min-priority queue with a Fibonacci heap, yielding a running time of O(V2 lg V + V E).

If negative-weight edges are allowed, Dijkstra's algorithm can no longer be used. Instead, we must run the slower Bellman-Ford algorithm once from each vertex. The resulting running time is O(V2E), which on a dense graph is O(V4). In this chapter we shall see how to do better. We shall also investigate the relation of the all-pairs shortest-paths problem to matrix multiplication and study its algebraic structure.

Unlike the single-source algorithms, which assume an adjacency-list representation of the graph, most of the algorithms in this chapter use an adjacency-matrix representation. (Johnson's algorithm for sparse graphs uses adjacency lists.) For convenience, we assume that the vertices are numbered 1, 2,..., |V|, so that the input is an n × n matrix W representing the edge weights of an n-vertex directed graph G = (V, E). That is, W = (wij), where

(25.1) |

Negative-weight edges are allowed, but we assume for the time being that the input graph contains no negative-weight cycles.

The tabular output of the all-pairs shortest-paths algorithms presented in this chapter is an n × n matrix D = (dij), where entry dij contains the weight of a shortest path from vertex i to vertex j. That is, if we let δ(i, j)denote the shortest-path weight from vertex i to vertex j (as in Chapter 24), then dij = δ(i, j) at termination.

To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor matrix Π = (πij), where πij is NIL if either i = j or there is no path from i to j, and otherwise πij is the predecessor of j on some shortest path from i. Just as the predecessor subgraph Gπ from Chapter 24 is a shortest-paths tree for a given source vertex, the subgraph induced by the ith row of the Π matrix should be a shortest-paths tree with root i. For each vertex i ∈ V , we define the predecessor subgraph of G for i as Gπi = (Vπ.i, Eπ.i) , where

Vπ.i = {j ∈ V : πij ≠ = NIL} ∪ {i}

and

Eπ.i = {(πij, J) : j ∈ Vπ.i - {i}}

If Gπ.i is a shortest-paths tree, then the following procedure, which is a modified version of the PRINT-PATH procedure from Chapter 22, prints a shortest path from vertex i to vertex j.

    PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j)
    1  if i = j
    2    then print i
    3    else if πij = NIL
    4         then print "no path from" i "to" j "exists"
    5         else PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, πij)
    6                     print j

In order to highlight the essential features of the all-pairs algorithms in this chapter, we won't cover the creation and properties of predecessor matrices as extensively as we dealt with predecessor subgraphs in Chapter 24. The basics are covered by some of the exercises.

| < Day Day Up > |