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 25, 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.*

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* = (

V_{}_{,i }= {jV:NIL} {_{ij}i}

E_{}_{,i}= {(,_{ij}j):jV_{}_{,i}andNIL}_{ij}_{.}

PRINT-ALL-PAIRS-SHORTEST-PATH(,i,j)

1ifi=j

2thenprinti

3else if= NIL_{ij}

4thenprint "no path from"i"to"j"exists"

5elsePRINT-ALL-PAIRS-SHORTEST-PATH(,i,)_{ij}

6 printj

This section presents a dynamic-programming algorithm for the all-pairs shortest-paths problem on a directed graph *G* = (*V, E*). Each major loop of the dynamic program will invoke an operation that is very similar to matrix multiplication, so that the algorithm will look like repeated matrix multiplication. We shall start by developing a (*V*^{4})-time algorithm for the all-pairs shortest-paths problem and then improve its running time to (*V*^{3} lg *V*).

1. Characterize the structure of an optimal solution.

2. Recursively define the value of an optimal solution.

3. Compute the value of an optimal solution in a bottom-up fashion.

We start by characterizing the structure of an optimal solution. For the all-pairs shortest-paths problem on a graph *G* = (*V, E*), we have proved (Lemma 25.1 ) that all subpaths of a shortest path are shortest paths.Supppose that the graph is represented by an adjacency matrix *W* = (*w _{ij}*). Consider a shortest path

The latter equality follows since *w _{jj}* = 0 for all

EXTEND-SHORTEST-PATHS(D,W)

1nrows[D]

2 letD' = (d') be an_{ij}nnmatrix

3fori1ton

4do forj1 ton

5dod'_{ij}

6fork1ton

7dod'min(_{ij}d', d_{ij}+_{ik}w)_{kj}

8returnD'

Observe that if we make the substitutions

d^{(m-1)}a,

wb,

d^{(m)}c ,

min + ,

+

MATRIX-MULTIPLY(A,B)

1nrows[A]

2 letCbe annnmatrix

3fori1ton

4do forj1ton

5doc0_{ij}

6fork1ton

7doc_{ij}c+_{ij}a_{ik }b_{kj}

8returnC

D^{(1) }=D^{(0)}W=W,

D^{(2) }=D^{(1)}W=W^{2},

D^{(3) }=D^{(2) }W=W^{3},

D^{(n-1) }=D^{(n-2) }^{ }W=W-1^{n}.

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)

1nrows[W]

2D^{(1)}W

3form2ton- 1

4doD^{(m)}EXTEND-SHORTEST-PATHS(D^{(m}-^{1)},W)

5returnD^{(n}-^{1)}

D^{(1) }=W,

D^{(2) }=W^{2}=WW,

D^{(4) }=W^{4}=W^{2 }W^{2}

D^{(8) }=W^{8}=W^{4 }W^{4},

D^{(2}^{lg(n-1)}^{) }=W^{2}^{lg(n-1)}^{ }=W^{2}^{lg(n-1)}^{-1}W^{2}^{lg(n-1)}^{-1}.

Since 2^{lg(n-1)} *n *- 1, the final product *D*^{(2}^{1g(n-1)}^{)} is equal to *D*^{(n-1)}.

The following procedure computes the above sequence of matrices by using this technique of * repeated squaring*.

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)

1nrows[W]

2D^{(1)}W

3m1

4whilen- 1 >m

5doD^{(2m)}EXTEND-SHORTEST-PATHS(D^{(m)},D^{(m)})

6m2m

7returnD^{(m)}

Why do we require that *w _{ii}* = 0 for all 1

used in the shortest-paths algorithms correspond to in regular matrix multiplication?

The FASTER-ALL-PAIRS-SHORTEST-PATHS procedure, as written, requires us to store lg(*n* - 1) matrices, each with *n*^{2} elements, for a total space requirement of (*n*^{2 }lg *n*). Modify the procedure to require only (*n*^{2}) space by using only two *n* *n* matrices.

Modify FASTER-ALL-PAIRS-SHORTEST-PATHS to detect the presence of a negative-weight cycle.

In this section, we shall use a different dynamic-programming formulation to solve the all-pairs shortest-paths problem on a directed graph *G* = (*V, E*). The resulting algorithm, known as the * Floyd-Warshall algorithm*, runs in (

In the Floyd-Warshall algorithm, we use a different characterization of the structure of a shortest path than we used in the matrix-multiplication-based all-pairs algorithms. The algorithm considers the "intermediate" vertices of a shortest path, where an * intermediate* vertex of a simple path

Based on recurrence (26.5), the following bottom-up procedure can be used to compute the values in order of increasing values of *k*. Its input is an *n* *n* matrix *W* defined as in equation (26.1). The procedure returns the matrix *D*^{(n)} of shortest-path weights.

Given a directed graph *G* = (*V*, *E*) with vertex set *V* = {1, 2, . . . , *n*}, we may wish to find out whether there is a path in *G* from *i* to *j* for all vertex pairs *i*, *j* *V*. The * transitive closure* of

*E** = {(*i*, *j*) : there is a path from vertex *i* to vertex *j* in *G*} .

As in the Floyd-Warshall algorithm, we compute the matrices in order of increasing *k*.

TRANSITIVE-CLOSURE(G)

Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure 26.2. Show the matrix *D*^{(k)} that results for each iteration of the outer loop.

FLOYD-WARSHALL'(W)

1nrows[W]

2DW

3fork1ton

4do fori1ton

5do forj1ton

6dmin(_{ij}d,_{ij}d+_{ik}d)_{kj}

7returnD

Suppose that we modify the way in which equality is handled in equation (26.7):

Is this alternative definition of the predecessor matrix correct?

How can the output of the Floyd-Warshall algorithm be used to detect the presence of a negative-weight cycle?

Give an *O*(*V E*)-time algorithm for computing the transitive closure of a directed graph *G* = (*V*, *E*).

Johnson's algorithm finds shortest paths between all pairs in *O*(*V*^{2} lg *V* + *V E*) time; it is thus asymptotically better than either repeated squaring of matrices or the Floyd-Warshall algorithm for sparse graphs. The algorithm either returns a matrix of shortest-path weights for all pairs or reports that the input graph contains a negative-weight cycle. Johnson's algorithm uses as subroutines both Dijkstra's algorithm and the Bellman-Ford algorithm, which are described in Chapter 25.

Johnson's algorithm uses the technique of * reweighting*, which works as follows. If all edge weights

2. For all edges (*u*, *v*), the new weight is nonnegative.

* Proof *We start by showing that

The third equality follows from the telescoping sum on the second line.

and thus *c* has negative weight using *w* if and only if it has negative weight using

This code simply performs the actions we specified earlier. Line 1 produces *G*'*.* Line 2 runs the Bellman-Ford algorithm on *G*' with weight function *w*. If *G*' , and hence *G*, contains a negative-weight cycle, line 3 reports the problem. Lines 4-11 assume that *G*' contains no negative-weight cycles. Lines 4-5 set *h*(*v*) to the shortest-path weight (*s*,* v*) computed by the Bellman-Ford algorithm for all *v ** V*'. Lines 6-7 compute the new weights . For each pair of vertices *u, v ** V*, the **for** loop of lines 8-11 computes the shortest-path weight by calling Dijkstra's algorithm once from each vertex in *V*. Line 11 stores in matrix entry *d _{uv}* the correct shortest-path weight

The running time of Johnson's algorithm is easily seen to be *O(V ^{2} *lg

What is the purpose of adding the new vertex *s* to *V*, yielding *V*'*?*

A* closed semiring* is a system where

*S *is * closed* under :

is **associative****:*** a* (*b * *c*) = (*a* * b*) *c *for all *a*,*b*,*c* *S.*

3. is **commutative:*** a * *b* = *b* *a* for all *a*, *b* *S.*

4. is **idempotent:*** a * *a* = *a* for all *a* *S.*

Although the closed-semiring properties may seem abstract, they can be related to a calculus of paths in directed graphs. Suppose we are given a directed graph *G = *(*V, E*) and a * labeling function* :

We use the associative extension operator to extend the notion of labels to paths. The **label of path***p = **v*_{1},* v*_{2, . . . ,}*v _{k}*

The identity serves as the label of the empty path.

Because the extension operator is associative, we can define the label of the concatenation of two paths in a natural way. Given paths *p*_{1} = *v*_{1}*,v*_{2}*, . . . ,v _{k}*

p_{1}_{}p_{2}=v_{1},v_{2}, . . . ,v,_{k}v+1, . . . ,_{k}v,_{l}

and the label of their concatenation is

The summary operator , which is both commutative and associative, is used to * summarize* path labels. That is, the value

We use a special notation to denote the label of a cycle that may be traversed any number of times. Suppose that we have a cycle *c *with label (*c*) = *a* We may traverse *c *zero times for a label of , once for a label of (*c*) = *a*, twice for a label of , and so on. The label we get by summarizing this infinite number of traversals of cycle *c *is the * closure* of

Thus, in Figure 26.8, we want to compute .

For the shortest-paths example, for any nonnegative real *a* **R**^{0 } {},

We have already seen one example of a closed semiring, namely *S*_{1} = (**R**^{0} {}, min, +, ,0), which we used for shortest paths with nonnegative edge weights. (As previously noted, the min operator actually returns the greatest lower bound of its arguments.) We have also shown that *a*^{*} = 0 for all *a* **R**^{0} {}.

Suppose we are given a directed graph *G* = (*V, E*) with labeling function : *V * *V * *S*. The vertices are numbered 1 through *n*. For each pair of vertices *i*, *j* *V*, we want to compute equation (26.11):

The dynamic-programming algorithm computes the values in order of increasing *k*. It returns the matrix *L*^{(n)} = .

Verify that *S*_{1} = (**R**^{0} {}, min, +, , 0) and *S*_{3} = ({0, 1}, V, , 0, 1) are closed semirings.

Rewrite the COMPUTE-SUMMARIES procedure to use closed semiring *S*_{2}, so that it implements the Floyd-Warshall algorithm. What should be the value of - +?

Is the system *S*_{4} = (**R**, +, , 0, 1) a closed semiring?

26-1 Transitive closure of a dynamic graph

Suppose that we wish to maintain the transitive closure of a directed graph *G = (V, E*) as we insert edges into *E*. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph *G *has no edges initially and that the transitive closure is to be represented as a boolean matrix.

26-2 Shortest paths in -dense graphs

A graph *G *= (*V, E*) is * -dense* if

26-3 Minimum spanning tree as a closed semiring

Let *G *= (*V, E*) be a connected, undirected graph with weight function *w* : E **R**. Let the vertex set be *V *= {1, 2, . . . , *n*}, where *n *= *V**,* and assume that all edge weights *w* (*i, j*) are unique. Let *T* be the unique (see Exercise 24.1-6) minimum spanning tree of *G*. In this problem, we shall determine *T* by using a closed semiring, as suggested by B. M. Maggs and S. A. Plotkin. We first determine, for each pair of vertices *i, j ** V*, the * minimax* weight

* a. *Briefly justify the assertion that

**b.** Give a recurrence for , where *k* 0.