chap25.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph that contains no negative-weight cycles. Let <I>s</I> <img src="../images/memof12.gif"> <I>V</I> be the source vertex, and let <I>G</I> be initialized by <FONT FACE="Courier New" SIZE=2>INITIALIZE</FONT>-<FONT FACE="Courier New" SIZE=2>SINGLE</FONT>-<FONT FACE="Courier New" SIZE=2>SOURCE</FONT>(<I>G, s</I>). Prove that there is a sequence of <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif"> - 1 relaxation steps that produces <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s ,v</I>) for all <I>v </I><img src="../images/memof12.gif"> <I>V</I>.<P>
<a name="08c8_17f2">25.1-8<a name="08c8_17f2"><P>
Let <I>G</I> be an arbitrary weighted, directed graph with a negative-weight cycle reachable from the source vertex <I>s</I>. Show that an infinite sequence of relaxations of the edges of <I>G</I> can always be constructed such that every relaxation causes a shortest-path estimate to change.<P>
<P>


<P>







<h1><a name="08c9_17ef">25.2 Dijkstra's algorithm<a name="08c9_17ef"></h1><P>
<a name="08c9_17ea"><a name="08c9_17eb"><a name="08c9_17ec"><a name="08c9_17ed">Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph <I>G</I> = (<I>V, E</I>) for the case in which all edge weights are nonnegative. In this section, therefore, we assume that <I>w</I>(<I>u, v</I>) <img src="../images/gteq.gif"> 0 for each edge (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E</I>.<P>
Dijkstra's algorithm maintains a set <I>S</I> of vertices whose final shortest-path weights from the source <I>s</I> have already been determined. That is, for all vertices <I>v</I> <img src="../images/memof12.gif"> <I>S</I>, we have <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, v</I>). The algorithm repeatedly selects the vertex <I>u</I> <img src="../images/memof12.gif"> <I>V</I> - <I>S</I> with the minimum shortest-path estimate, inserts <I>u</I> into <I>S</I>, and relaxes all edges leaving <I>u</I>. In the following implementation, we maintain a priority queue <I>Q</I> that contains all the vertices in <I>V - S</I>, keyed by their <I>d</I> values. The implementation assumes that graph <I>G</I> is represented by adjacency lists.<P>
<pre><a name="08c9_17ee">DIJKSTRA(<I>G,w,s</I>)</sub></sup></pre><P>
<pre>1  INITIALIZE-SINGLE-SOURCE (<I>G,s</I>)</sub></sup></pre><P>
<pre>2  <img src="527_a.gif"></sub></sup></pre><P>
<pre>3  <I>Q</I> <img src="../images/arrlt12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>4  <B>while</B> <img src="527_b.gif"></sub></sup></pre><P>
<pre>5<B>       do</B> <I>u</I> <img src="../images/arrlt12.gif"> EXTRACT-MIN(<I>Q)</I></sub></sup></pre><P>
<pre>6          <I>S</I> <img src="../images/arrlt12.gif"> <I>S</I> <img src="../images/wideu.gif"> {<I>u</I>}</sub></sup></pre><P>
<pre>7<B>          for</B> each vertex <I>v</I> <img src="../images/memof12.gif"> <I>Adj</I>[<I>u</I>]</sub></sup></pre><P>
<pre>8              <B>do</B> RELAX (<I>u</I>,<I>v</I>,<I>w</I>)</sub></sup></pre><P>
<img src="528_a.gif"><P>
<h4><a name="08c9_17f0">Figure 25.5 The execution of Dijkstra's algorithm. The source is the leftmost vertex. The shortest-path estimates are shown within the vertices, and shaded edges indicate predecessor values: if edge (u,v) is shaded, then <img src="../images/piuc.gif">[v] = u. Black vertices are in the set S, and white vertices are in the priority queue Q = V - S. (a) The situation just before the first iteration of the while loop of lines 4-8. The shaded vertex has the minimum d value and is chosen as vertex u in line 5. (b)-(f) The situation after each successive iteration of the while loop. The shaded vertex in each part is chosen as vertex u in line 5 of the next iteration. The d and <img src="../images/piuc.gif"> values shown in part (f) are the final values.<a name="08c9_17f0"></sub></sup></h4><P>
Dijkstra's algorithm relaxes edges as shown in Figure 25.5. Line 1 performs the usual initialization of <I>d</I> and <img src="../images/piuc.gif"> values, and line 2 initializes the set <I>S</I> to the empty set. Line 3 then initializes the priority queue <I>Q</I> to contain all the vertices in <img src="528_b.gif">.<I> </I>Each time through the <B>while</B> loop of lines 4-8, a vertex <I>u</I> is extracted from <I>Q = V - S</I> and inserted into set <I>S</I>. (The first time through this loop, <I>u = s</I>.) Vertex <I>u</I>, therefore, has the smallest shortest-path estimate of any vertex in <I>V - S</I>. Then, lines 7-8 relax each edge (<I>u, v</I>) leaving <I>u</I>, thus updating the estimate <I>d</I>[<I>v</I>] and the predecessor <img src="../images/piuc.gif">[<I>v</I>] if the shortest path to <I>v</I> can be improved by going through <I>u</I>. Observe that vertices are never inserted into <I>Q</I> after line 3 and that each vertex is extracted from <I>Q</I> and inserted into <I>S</I> exactly once, so that the <B>while</B> loop of lines 4-8 iterates exactly <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif"> times.<P>
Because Dijkstra's algorithm always chooses the &quot;lightest&quot; or &quot;closest&quot; vertex in <I>V</I> - <I>S</I> to insert into set <I>S</I>, we say that it uses a greedy strategy. Greedy strategies are presented in detail in Chapter 17, but you need not have read that chapter to understand Dijkstra's algorithm. Greedy strategies do not always yield optimal results in general, but as the following theorem and its corollary show, Dijkstra's algorithm does indeed compute shortest paths. The key is to show that each time a vertex <I>u</I> is inserted into set <I>S</I>, we have <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I>(</I>s, u<I>).</I><P>
<img src="529_a.gif"><P>
<h4><a name="08c9_17f1">Figure 25.6 The proof of Theorem 25.10. Set S is nonempty just before vertex u is inserted into it. A shortest path p from source s to vertex u can be decomposed into <img src="529_b.gif"> where y is the first vertex on the path that is not in V - S and x <img src="../images/memof12.gif"> S immediately precedes y. Vertices x and y are distinct, but we may have s = x or y = u. Path p<SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2> may or may not reenter set S.<a name="08c9_17f1"></FONT></sub></sup></h4><P>
<a name="08c9_17f2">Theorem 25.10<a name="08c9_17f2"><P>
If we run Dijkstra's algorithm on a weighted, directed graph <I>G</I> = (<I>V</I>, <I>E</I>) with nonnegative weight function <I>w</I> and source <I>s</I>, then at termination, <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I>(</I>s, u<I>) for all vertices </I>u<I> <img src="../images/memof12.gif"> </I>V<I>.</I><P>
<I><B>Proof     </I></B>We shall show that for each vertex <I>u</I> <img src="../images/memof12.gif"> <I>V,</I> we have <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, u</I>) at the time when <I>u</I> is inserted into set <I>S</I> and that this equality is maintained thereafter.<P>
For the purpose of contradiction, let <I>u</I> be the first vertex for which <I>d</I>[<I>u</I>] <img src="../images/noteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>) when it is inserted into set <I>S</I>. We shall focus our attention on the situation at the beginning of the iteration of the <B>while</B> loop in which <I>u</I> is inserted into <I>S</I> and derive the contradiction that <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, u</I>) at that time by examining a shortest path from <I>s</I> to <I>u</I>. We must have <I>u</I> <img src="../images/noteq.gif"> <I>s</I> because <I>s</I> is the first vertex inserted into set <I>S</I> and <I>d</I>[<I>s</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, s</I>) = 0 at that time. Because <I>u</I> <img src="../images/noteq.gif"> <I>s</I>, we also have that <img src="529_c.gif"> just before <I>u</I> is inserted into <I>S</I>. There must be some path from <I>s</I> to <I>u</I>, for otherwise <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>) = <img src="../images/infin.gif">by Corollary 25.6, which would violate our assumption that <I>d</I>[<I>u</I>] <img src="../images/noteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>). Because there is at least one path, there is a shortest path <I>p fr</I>om <I>s </I>to <I>u</I>. Path <I>p</I> connects a vertex in <I>S</I>, namely <I>s</I>, to a vertex in <I>V</I> - <I>S</I>, namely <I>u</I>. Let us consider the first vertex <I>y</I> along <I>p</I> such that <I>y</I> <img src="../images/memof12.gif"> <I>V</I> - <I>S</I>, and let <I>x</I> <img src="../images/memof12.gif"> <I>V</I> be <I>y</I>'s predecessor. Thus, as shown in Figure 25.6, path <I>p</I> can be decomposed as <img src="529_d.gif"><P>
We claim that <I>d</I>[<I>y</I>] = <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>y</I>) when <I>u</I> is inserted into <I>S</I>. To prove this claim, observe that <I>x</I> <img src="../images/memof12.gif"> <I>S</I>. Then, because <I>u</I> is chosen as the first vertex for which <I>d</I>[<I>u</I>] <img src="../images/noteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>) when it is inserted into <I>S</I>, we had <I>d</I>[<I>x</I>] = <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>x</I>) when x was inserted into <I>S</I>. Edge (<I>x</I>, <I>y</I>) was relaxed at that time, so the claim follows from Lemma 25.7.<P>
We can now obtain a contradiction to prove the theorem. Because <I>y</I> occurs before <I>u</I> on a shortest path from <I>s</I> to <I>u</I> and all edge weights are  nonnegative (notably those on path <I>p</I><SUB>2</SUB>), we have <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>y</I>) <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>), and thus<P>
<pre><I>d</I>[<I>y</I>]  =  <img src="../images/delta12.gif"><I>(</I>s<I>, </I>y<I>)</I></sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">  <img src="../images/delta12.gif"><I>(</I>s<I>, </I>u<I>)</I></sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">  <I>d</I>[<I>u</I>]     (by Lemma 25.5).</sub></sup></pre><P>
<h4><a name="08c9_17f3">(25.2)<a name="08c9_17f3"></sub></sup></h4><P>
But because both vertices <I>u</I> and <I>y</I> were in <I>V</I> - <I>S</I> when <I>u</I> was chosen in line 5, we have <I>d</I>[<I>u</I>] <img src="../images/lteq12.gif"> <I>d</I>[<I>y</I>]. Thus, the two inequalities in (25.2) are in fact equalities, giving<P>
<pre><I>d</I>[<I>y</I>] = <img src="../images/delta12.gif"><I>(</I>s<I>, </I>y<I>) = <img src="../images/delta12.gif"></I>(<I>s</I>, <I>u</I>) = <I>d</I>[<I>u</I>] .</sub></sup></pre><P>
Consequently, <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>), which contradicts our choice of <I>u</I>. We conclude that at the time each vertex <I>u</I> <img src="../images/memof12.gif"> <I>V</I> is inserted into set <I>S</I>, we have <I>d</I>[<I>u</I>] = (<I>s</I>, <I>u</I>), and by Lemma 25.5, this equality holds thereafter.      <P>
<a name="08c9_17f4">Corollary 25.11<a name="08c9_17f4"><P>
If we run Dijkstra's algorithm on a weighted, directed graph <I>G</I> = (<I>V</I>, <I>E</I>) with nonnegative weight function <I>w</I> and source <I>s</I>, then at termination, the predecessor subgraph <I>G</I><img src="../images/piuc.gif"> is a shortest-paths tree rooted at <I>s</I>.<P>
<I><B>Proof     </I></B>Immediate from Theorem 25.10 and Lemma 25.9.      <P>





<h2>Analysis</h2><P>
<a name="08ca_17ef">How fast is Dijkstra's algorithm? Consider first the case in which we maintain the priority queue <I>Q</I> = <I>V </I>- <I>S</I> as a linear array. For such an implementation, each <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> operation takes time <I>O</I>(<I>V</I>), and there are |V<I>|</I> such operations, for a total <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> time of <I>O</I>(<I>V</I><SUP>2</SUP>)<I>. </I>Each<I> </I>vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I> is inserted into set <I>S</I> exactly once, so each edge in the adjacency list <I>Adj</I>[<I>v</I>] is examined in the <B>for</B> loop of lines 4-8 exactly once during the course of the algorithm. Since the total number of edges in all the adjacency lists is |E<I>|</I>, there are a total of |E<I>|</I> iterations of this <B>for </B>loop, with each iteration taking <I>O</I>(1) time. The running time of the entire algorithm is thus <I>O</I>(<I>V</I><SUP>2</SUP> + <I>E</I>) = <I>O</I>(<I>V</I><SUP>2</SUP>).<P>
<a name="08ca_17f0"><a name="08ca_17f1">If the graph is sparse, however, it is practical to implement the priority queue <I>Q</I> with a binary heap. The resulting algorithm is sometimes called the <I><B>modified Dijkstra algorithm</I></B>. Each <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> operation then takes time <I>O</I>(lg <I>V</I>). As before, there are |V<I>|</I> such operations. The time to build the binary heap is <I>O</I>(<I>V</I>). The assignment <I>d</I>[<I>v</I>] <img src="../images/arrlt12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>) in R<FONT FACE="Courier New" SIZE=2>ELAX </FONT>is accomplished by the call <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>(<I>Q</I>, <I>v</I>, <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>)), which takes time <I>O</I>(lg <I>V</I>) (see Exercise 7.5-4), and there are still at most |E<I>|</I> such operations. The total running time is therefore <I>O</I>((<I>V</I> + <I>E</I>) lg <I>V</I>), which is <I>O</I>(<I>E</I> lg <I>V</I>) if all vertices are reachable from the source.<P>
<a name="08ca_17f2"><a name="08ca_17f3">We can in fact achieve a running time of <I>O</I>(<I>V</I> lg <I>V </I>+ <I>E</I>) by implementing the priority queue <I>Q</I> with a Fibonacci heap (see Chapter 21). The amortized cost of each of the |V<I>|</I> <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> operations is <I>O</I>(lg <I>V</I>), and each of the |E<I>|</I> <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-K<FONT FACE="Courier New" SIZE=2>EY </FONT>calls takes only <I>O</I>(1) amortized time. Historically, the development of Fibonacci heaps was motivated by the observation that in the modified Dijkstra algorithm there are potentially many more <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-K<FONT FACE="Courier New" SIZE=2>EY </FONT>calls than <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> calls, so any method of reducing the amortized time of each <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> operation to <I>o</I>(lg <I>V</I>) without increasing the amortized time of <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New"