📄 chap26.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 26: ALL-PAIRS SHORTEST PATHS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap27.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap25.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="08d8_183c">CHAPTER 26: ALL-PAIRS SHORTEST PATHS<a name="08d8_183c"></h1><P>
<a name="08d8_1835"><a name="08d8_1836"><a name="08d8_1837">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 <I>G</I> = (<I>V</I>, <I>E</I>) with a weight function <I>w</I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B> that maps edges to real-valued weights. We wish to find, for every pair of vertices <I>u</I>, <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, a shortest (least-weight) path from <I>u</I> to <I>v</I>, 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 <I>u</I>'s row and <I>v</I>'s column should be the weight of a shortest path from <I>u</I> to <I>v.</I><P>
We can solve an all-pairs shortest-paths problem by running a single-source shortest-paths algorithm <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif"> 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 priority queue, the running time is <I>O</I>(<I>V</I><SUP>3</SUP> + <I>VE</I>) = <I>O</I>(<I>V</I><SUP>3</SUP>). The binary-heap implementation of the priority queue yields a running time of <I>O</I>(<I>V E </I>lg <I>V</I>), which is an improvement if the graph is sparse. Alternatively, we can implement the priority queue with a Fibonacci heap, yielding a running time of <I>O</I>(<I>V</I><SUP>2</SUP> lg <I>V</I> + <I>VE</I>).<P>
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 <I>O</I>(<I>V</I><SUP>2 </SUP><I>E</I>), which on a dense graph is <I>O</I>(<I>V</I><SUP>4</SUP>). 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.<P>
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.) The input is an <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrix <I>W</I> representing the edge weights of an <I>n</I>-vertex directed graph <I>G</I> = (<I>V</I>, <I>E</I>). That is, <I>W</I> = (<I>w<SUB>ij</I></SUB>), where<P>
<img src="550_a.gif"><P>
<h4><a name="08d8_183d">(26.1)<a name="08d8_183d"></sub></sup></h4><P>
Negative-weight edges are allowed, but we assume for the time being that the input graph contains no negative-weight cycles.<P>
The tabular output of the all-pairs shortest-paths algorithms presented in this chapter is an <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrix <I>D</I> = (<I>d<SUB>ij</I></SUB>), where entry <I>d<SUB>ij</I></SUB> contains the weight of a shortest path from vertex <I>i</I> to vertex <I>j</I>. That is, if we let <img src="../images/delta12.gif">(<I>i,j</I>) denote the shortest-path weight from vertex <I>i</I> to vertex <I>j</I> (as in Chapter 25), then <I>dij</I> = <img src="../images/delta12.gif">(<I>i,j</I>) at termination.<P>
<a name="08d8_1838"><a name="08d8_1839"><a name="08d8_183a">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 <I><B>predecessor matrix</I></B> <img src="../images/piuc.gif"> = (<img src="../images/piuc.gif"><I><SUB>ij</I></SUB> ), where <img src="../images/piuc.gif"><I><SUB>ij</I></SUB> is <FONT FACE="Courier New" SIZE=2>NIL</FONT> if either <I>i </I>=<I> j</I> or there is no path from <I>i</I> to <I>j</I>, and otherwise <img src="../images/piuc.gif"><I><SUB>ij</I></SUB> is some predecessor of <I>j</I> on a shortest path from <I>i</I>. Just as the predecessor subgraph <I>G</I><img src="../images/piuc.gif"> from Chapter 25 is a shortest-paths tree for a given source vertex, the subgraph induced by the <I>i</I>th row of the <img src="../images/piuc.gif"> matrix should be a shortest-paths tree with root <I>i</I>. For each vertex <I>i</I> <img src="../images/memof12.gif"> <I>V</I>, we define the <I><B>predecessor subgraph</I></B> of <I>G</I> for <I>i</I> as <I>G</I><img src="../images/piuc.gif"><SUB>,<I>i </I></SUB>= (<I>V</I><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB>, <I>E</I><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB>), where<P>
<pre><I>V</I><SUB></SUB><img src="../images/piuc.gif"><SUB>,<I>i </I></SUB>= {<I>j</I> <img src="../images/memof12.gif"> <I>V</I> : <img src="../images/piuc.gif"><I><SUB>ij</I> </SUB><img src="../images/noteq.gif"> NIL} <img src="../images/wideu.gif"> {<I>i</I>}</sub></sup></pre><P>
and<P>
<pre><I>E</I><SUB></SUB><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB> = {(<img src="../images/piuc.gif"><I><SUB>ij</I></SUB>, <I>j</I>): <I>j</I> <img src="../images/memof12.gif"> <I>V</I><SUB></SUB><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB> and <img src="../images/piuc.gif"><I><SUB>ij</I> </SUB><img src="../images/noteq.gif"> NIL} <SUB>.</sub></sup></pre><P>
If <I>G</I><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB> is a shortest-paths tree, then the following procedure, which is a modified version of the <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>PATH</FONT> procedure from Chapter 23, prints a shortest path from vertex <I>i</I> to vertex <I>j.</I><P>
<pre><a name="08d8_183b">PRINT-ALL-PAIRS-SHORTEST-PATH(<img src="../images/piuc.gif">,<I>i</I>,<I>j</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>i</I> = <I>j</I></sub></sup></pre><P>
<pre>2 <B>then</B> print <I>i</I></sub></sup></pre><P>
<pre>3 <B>else if</B> <img src="../images/piuc.gif"><I><SUB>ij</I></SUB> = NIL</sub></sup></pre><P>
<pre>4 <B>then</B> print "no path from" <I>i</I> "to" <I>j</I> "exists"</sub></sup></pre><P>
<pre>5 <B>else</B> PRINT-ALL-PAIRS-SHORTEST-PATH(<img src="../images/piuc.gif">,<I>i</I>,<img src="../images/piuc.gif"><I><SUB>ij</I></SUB>)</sub></sup></pre><P>
<pre>6 print <I>j</I></sub></sup></pre><P>
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 25. The basics are covered by some of the exercises.<P>
<h2>Chapter outline</h2><P>
Section 26.1 presents a dynamic-programming algorithm based on matrix multiplication to solve the all-pairs shortest-paths problem. Using the technique of "repeated squaring," this algorithm can be made to run in <img src="../images/bound.gif">(<I>V</I><SUP>3 </SUP>1g <I>V</I>) time. Another dynamic-programming algorithm, the Floyd-Warshall algorithm, is given in Section 26.2. The Floyd-Warshall algorithm runs in time <img src="../images/bound.gif">(<I>V</I><SUP>3</SUP>). Section 26.2 also covers the problem of finding the transitive closure of a directed graph, which is related to the all-pairs shortest-paths problem. Johnson's algorithm is presented in Section 26.3. Unlike the other algorithms in this chapter, Johnson's algorithm uses the adjacency-list representation of a graph. It solves the all-pairs shortest-paths problem in <I>O</I>(<I>V</I><SUP>2</SUP> lg <I>V</I> + <I>V E</I>) time, which makes it a good algorithm for large, sparse graphs. Finally, in Section 26.4, we examine an algebraic structure called a "closed semiring," which allows many shortest-paths algorithms to be applied to a host of other all-pairs problems not involving shortest paths.<P>
Before proceeding, we need to establish some conventions for adjacency-matrix representations. First, we shall generally assume that the input graph <I>G</I> = (<I>V, E</I>) has <I>n</I> vertices, so that <I>n</I> = <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif">. Second, we shall use the convention of denoting matrices by uppercase letters, such as <I>W</I> or <I>D</I>, and their individual elements by subscripted lowercase letters, such as <I>w<SUB>ij </I></SUB>or <I>d<SUB>ij</I></SUB>. Some matrices will have parenthesized superscripts, as in <I>D</I><SUP>(<I>m</I>) </SUP>= <img src="552_a.gif">, to indicate iterates. Finally, for a given <I>n <img src="../images/mult.gif"> n</I> matrix <I>A</I>, we shall assume that the value of <I>n</I> is stored in the attribute <I>rows</I>[<I>A</I>].<P>
<P>
<h1><a name="08db_1840">26.1 Shortest paths and matrix multiplication<a name="08db_1840"></h1><P>
<a name="08db_183c"><a name="08db_183d"><a name="08db_183e"><a name="08db_183f">This section presents a dynamic-programming algorithm for the all-pairs shortest-paths problem on a directed graph <I>G</I> = (<I>V, E</I>). 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 <img src="../images/bound.gif">(<I>V</I><SUP>4</SUP>)-time algorithm for the all-pairs shortest-paths problem and then improve its running time to <img src="../images/bound.gif">(<I>V</I><SUP>3</SUP> lg <I>V</I>).<P>
Before proceeding, let us briefly recap the steps given in Chapter 16 for developing a dynamic-programming algorithm.<P>
1. Characterize the structure of an optimal solution.<P>
2. Recursively define the value of an optimal solution.<P>
3. Compute the value of an optimal solution in a bottom-up fashion.<P>
(The fourth step, constructing an optimal solution from computed information, is dealt with in the exercises.)<P>
<h2>The structure of a shortest path</h2><P>
<a name="08dc_1840">We start by characterizing the structure of an optimal solution. For the all-pairs shortest-paths problem on a graph <I>G</I> = (<I>V, E</I>), 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 <I>W</I> = (<I>w<SUB>ij</I></SUB>). Consider a shortest path <I>p</I> from vertex <I>i</I> to vertex <I>j</I>, and suppose that <I>p</I> containsat most <I>m</I> edges. Assuming that there are no negative-weight cycles, <I>m</I> is finite. If <I>i</I> = <I>j</I>, then <I>p</I> has weight 0 and no edges. If vertices <I>i</I> and <I>j</I> are distinct, then we decompose path <I>p</I> into <img src="553_a.gif">, where path <I>p</I>' now contains at most <I>m</I> - 1 edges. Moreover, by Lemma 25.1, <I>p'</I> is a shortest path from <I>i</I> to <I>k</I>. Thus, by Corollary 25.2, we have <img src="../images/delta12.gif">(<I>i, j</I>) = <img src="../images/delta12.gif">(<I>i, k</I>) + <I>w<SUB>kj</I></SUB>.<P>
<P>
<h2>A recursive solution to the all-pairs shortest-paths problem</h2><P>
Now, let <img src="553_b.gif"> be the minimum weight of any path from vertex <I>i</I> to vertex <I>j </I>that contains at most <I>m</I> edges. When <I>m</I> = 0, there is a shortest path from <I>i </I>to <I>j</I> with no edges if and only if <I>i</I> = <I>j</I>. Thus,<P>
<img src="553_c.gif"><P>
For <I>m</I> <img src="../images/gteq.gif"> 1, we compute <img src="553_d.gif"> as the minimum of <img src="553_e.gif"> (the weight of the shortest path from <I>i</I> to <I>j</I> consisting of at most <I>m</I> - 1 edges) and the minimum weight of any path from <I>i</I> to <I>j</I> consisting of at most <I>m</I> edges, obtained by looking at all possible predecessors <I>k</I> of <I>j</I>. Thus, we recursively define<P>
<img src="553_f.gif"><P>
<h4><a name="08dd_0001">(26.2)<a name="08dd_0001"></sub></sup></h4><P>
The latter equality follows since <I>w<SUB>jj</I></SUB> = 0 for all <I>j</I>.<P>
What are the actual shortest-path weights <img src="../images/delta12.gif">(<I>i, j</I>)? If the graph contains no negative-weight cycles, then all shortest paths are simple and thus contain at most <I>n</I> - 1 edges. A path from vertex <I>i</I> to vertex <I>j</I> with more than <I>n</I> - 1 edges cannot have less weight than a shortest path from <I>i</I> to <I>j</I>. The actual shortest-path weights are therefore given by<P>
<img src="553_g.gif"><P>
<h4><a name="08dd_0002">(26.3)<a name="08dd_0002"></sub></sup></h4><P>
<P>
<h2>Computing the shortest-path weights bottom up</h2><P>
Taking as our in put the matrix <I>W</I> = (<I>w<SUB>ij</I></SUB>), we now compute a series of matrices <I>D</I><SUP>(1)</SUP>, <I>D</I><SUP>(2)</SUP>, . . . , <I>D</I><SUP>(<I>n</I>-1<I>)</I>,</SUP><SUB> </SUB>where for <I>m</I><SUB> </SUB>=<SUB> </SUB>1, 2, . . . <I>n</I><FONT FACE="Courier New" SIZE=2> </FONT>- 1,<SUB>,</SUB> we have <img src="553_h.gif">. The final matrix <I>D</I><SUP>(<I>n</I>-1) </SUP>contains the actual shortest-path weights. Observe that since <img src="553_i.gif"> for all vertices <I>i</I>, <I>j</I> <img src="../images/memof12.gif"> <I>V</I>, we have <I>D</I><SUP>(1)</SUP> = <I>W</I>.<P>
The heart of the algorithm is the following procedure, which, given matrices <I>D</I><SUP>(<I>m</I>-1)</SUP> and <I>W</I>, returns the matrix <I>D</I><SUP>(<I>m</I>)</SUP>. That is, it extends the shortest paths computed so far by one more edge.<P>
<pre><a name="08de_1841">EXTEND-SHORTEST-PATHS(<I>D</I>,<I>W</I>)</sub></sup></pre><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -