chap25.htm

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

<pre><I>E</I><SUB></SUB><img src="../images/piuc.gif"><SUB> = {(<img src="../images/piuc.gif">[<I>v</I>], <I>v</I>) <img src="../images/memof12.gif"> <I>E</I> : <I>v</I> <img src="../images/memof12.gif"> <I>V</I></SUB><SUB><img src="../images/piuc.gif"></SUB><I> - </I>{<I><img src="../images/sum14.gif"></I>}}. </sub></sup></pre><P>
<a name="08c1_17de"><a name="08c1_17df">We shall prove that the <img src="../images/piuc.gif"><I></I> values produced by the algorithms in this chapter have the property that at termination <I>G<FONT FACE="Courier New" SIZE=2></I><img src="../images/piuc.gif"><I></I></FONT> is a &quot;shortest-paths tree&quot;--informally, a rooted tree containing a shortest path from a source <I>s</I> to every vertex that is reachable from <I>s</I>. A shortest-paths tree is like the breadth-first tree from Section 23.2, but it contains shortest paths from the source defined in terms of edge weights instead of numbers of edges. To be precise, let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with weight function <I>w</I> : <I>E</I> <img src="../images/arrow12.gif"> <B>R</B>, and assume that <I>G</I> contains no negative-weight cycles reachable from the source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I>, so that shortest paths are well defined. A <I><B>shortest-paths tree</I></B> rooted at <I>s</I> is a directed subgraph <I>G</I><I>'</I> = ( <I>V</I><I>'</I>, <I>E</I><I>'</I>), where <I>V</I>'<I> <img src="../images/rgtubar.gif"> </I><I>V</I> and <I>E</I>'<I> <img src="../images/rgtubar.gif"></I> <I>E</I>, such that<P>
1.     <I>V</I><I>'</I> is the set of vertices reachable from <I>s</I> in <I>G</I>,<P>
2.     <I>G</I><I>'</I> forms a rooted tree with root <I>s</I>, and<P>
3.     for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I><I>'</I>, the unique simple path from <I>s</I> to <I>v</I> in <I>G</I><I>'</I> is a shortest path from <I>s</I> to <I>v</I> in <I>G</I>.<P>
Shortest paths are not necessarily unique, and neither are shortest-paths trees. For example, Figure 25.2 shows a weighted, directed graph and two shortest-paths trees with the same root.<P>
<P>







<h2>Chapter outline</h2><P>
The single-source shortest-paths algorithms in this chapter are all based on a technique known as relaxation. Section 25.1 begins by proving some important properties of shortest paths in general and then proves some important facts about relaxation-based algorithms. Dijkstra's algorithm, which solves the single-source shortest-paths problem when all edges have nonnegative weight, is given in Section 25.2. Section 25.3 presents the Bellman-Ford algorithm, which is used in the more general case in which edges can have negative weight. If the graph contains a negative-weight cycle reachable from the source, the Bellman-Ford algorithm detects its presence. Section 25.4 gives a linear-time algorithm for computing shortest paths from a single source in directed acyclic graphs. Finally, Section 25.5 shows how the Bellman-Ford algorithm can be used to solve a special case of &quot;linear programming.&quot;<P>
<img src="518_a.gif"><P>
<h4><a name="08c2_0001">Figure 25.2 (a) A weighted, directed graph with shortest-path weights from source s. (b) The shaded edges form a shortest-paths tree rooted at the source s. (c) Another shortest-paths tree with the same root.<a name="08c2_0001"></sub></sup></h4><P>
Our analysis will require some conventions for doing arithmetic with infinities. We shall assume that for any real number <I>a</I> <img src="../images/noteq.gif"> -<img src="../images/infin.gif">, we have <I>a</I> + <img src="../images/infin.gif"> = <img src="../images/infin.gif"> + <I>a</I> = <img src="../images/infin.gif">. Also, to make our proofs hold in the presence of negative-weight cycles, we shall assume that for any real number <I>a</I> <img src="../images/noteq.gif"> <img src="../images/infin.gif">, we have <I>a</I> + (-<img src="../images/infin.gif">) = (-<img src="../images/infin.gif">) + <I>a</I> = -<img src="../images/infin.gif">.<P>
<P>







<h1><a name="08c3_0001">25.1 Shortest paths and relaxation<a name="08c3_0001"></h1><P>
To understand single-source shortest-paths algorithms, it is helpful to understand the techniques that they use and the properties of shortest paths that they exploit. The main technique used by the algorithms in this chapter is relaxation, a method that repeatedly decreases an upper bound on the actual shortest-path weight of each vertex until the upper bound equals the shortest-path weight. In this section, we shall see how relaxation works and formally prove several properties it maintains.<P>
On a first reading of this section, you may wish to omit proofs of theorems--reading only their statements--and then proceed immediately to the algorithms in Sections 25.2 and 25.3. Pay particular attention, however, to Lemma 25.7, which is a key to understanding the shortest-paths algorithms in this chapter. On a first reading, you may also wish to ignore completely the lemmas concerning predecessor subgraphs and shortest-paths trees (Lemmas 25.8 and 25.9), concentrating instead on the earlier lemmas, which pertain to shortest-path weights.<P>





<h2>Optimal substructure of a shortest path</h2><P>
<a name="08c4_17e0"><a name="08c4_17e1">Shortest-paths algorithms typically exploit the property that a shortest path between two vertices contains other shortest paths within it. This optimal-substructure property is a hallmark of the applicability of both dynamic programming (Chapter 16) and the greedy method (Chapter 17). In fact, Dijkstra's algorithm is a greedy algorithm, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices (see Chapter 26), is a dynamic-programming algorithm. The following lemma and its corollary state the optimal-substructure property of shortest paths more precisely.<P>
<a name="08c4_17e2">Lemma 25.1<a name="08c4_17e2"><P>
Given a weighted, directed graph <I>G</I> = (<I>V</I>,<I> E</I>) with weight function <I>w</I>: <I>E </I><img src="../images/arrow12.gif"> <I><B>R</B>, let </I>p<I> = <img src="../images/lftwdchv.gif"></I>v<I><SUB>1</SUB>, </I>v<I><SUB>2</SUB></I>, . . . , v<SUB>k<I></SUB><img src="../images/wdrtchv.gif"></I> be a shortest path from vertex <I>v</I><SUB>1</SUB>, to vertex <I>v<SUB>k</I></SUB> and, for any <I>i</I> and <I>j</I> such that 1 <U>&lt;</U> <I>i</I> <U>&lt;</U> <I>j</I> <U>&lt;</U> <I>k</I>, let <I>p<SUB>ij</I></SUB> = <img src="../images/lftwdchv.gif"><I>v<SUB>i</I></SUB>,<I> v<SUB>i</I>+1</SUB>, . . . , <I>v<SUB>i</I></SUB><img src="../images/wdrtchv.gif"> be the subpath of <I>p</I> from vertex <I>v<SUB>i</I></SUB>, to vertex <I>v<SUB>j</I></SUB>. Then, <I>p<SUB>ij</I></SUB> is a shortest path from <I>v<SUB>i</I></SUB> to <I>v<SUB>j</I></SUB>.<P>
<I><B>Proof     </I></B>If we decompose path <I>p</I> into <img src="519_a.gif"> then <I>w</I>(<I>p</I>) = <I>w</I>(<I>p</I><SUB>1<I>i</I></SUB>) + <I>w</I>(<I>p<SUB>ij</I></SUB>) + <I>w</I>(<I>p<SUB>jk</I></SUB>). Now, assume that there is a path <I>p</I><I>'<SUB>ij</I></SUB> from <I>v<SUB>i</I></SUB> to <I>v<SUB>j</I></SUB> with weight <I>w</I>(<I>p</I><I>'<SUB>ij</I></SUB>) &lt; <I>w(p<SUB>ij</SUB>)</I>. Then, <I><img src="519_b.gif"> </I>is a path<I> </I>from<I> v<SUB>1</I></SUB> to <I>v<SUB>k</I></SUB> whose weight <I>w</I>(<I>p</I><SUB>1<I>i</I></SUB>) + <I>w</I>(<I>p</I><I>'<SUB>ij</I></SUB>) + <I>w</I>(<I>p<SUB>jk</I></SUB>) is less than <I>w</I>(<I>p</I>), which contradicts the premise that <I>p</I> is a shortest path from <I>v</I><SUB>1</SUB> to <I>v<SUB>k..     </I></SUB> <P>
In studying breadth-first search (Section 23.2), we proved as Lemma 23.1 a simple property of shortest distances in unweighted graphs. The following corollary to Lemma 25.1 generalizes the property to weighted graphs.<P>
<a name="08c4_17e3">Corollary 25.2<a name="08c4_17e3"><P>
Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with weight function <I>w </I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B>. Suppose that a shortest path <I>p</I> from a source s to a vertex <I>v</I> can be decomposed into <img src="519_c.gif"> for some vertex <I>u</I> and path <I>p</I><I>'</I>. Then, the weight of a shortest path from <I>s</I> to <I>v</I> is <img src="../images/delta12.gif"><I> (</I>s, v<I>) = <img src="../images/delta12.gif"></I> (<I>s, u</I>) + <I>w</I>(<I>u, v</I>).<P>
<I><B>Proof     </I></B>By Lemma 25.1, subpath <I>p</I><I>'</I> is a shortest path from source <I>s</I> to vertex <I>u</I>. Thus,<P>
<pre><img src="../images/delta12.gif">(<I>s</I>, <I>v</I>)   =  <I>w</I>(<I>p</I>)</sub></sup></pre><P>
<pre>=  w(p') + w(u, v)</sub></sup></pre><P>
<pre>=  <img src="../images/delta12.gif">(s, u) + w(u, v).      </sub></sup></pre><P>
The next lemma gives a simple but useful property of shortest-path weights.<P>
<a name="08c4_17e4">Lemma 25.3<a name="08c4_17e4"><P>
Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph <I>G</I> = (<I>V, E</I>) with weight function <I>w</I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B> and source vertex <I>s</I>. 0Then, for all edges (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E</I>, we have <img src="../images/delta12.gif"><I>(</I>s, v<I>) <U>&lt;</U> <img src="../images/delta12.gif"></I> (<I>s, u</I>) + <I>w</I>(<I>u, v</I>).<P>
<I><B>Proof     </I></B>A shortest path <I>p</I> from source <I>s</I> to vertex <I>v</I> has no more weight than any other path from <I>s</I> to <I>v</I>. Specifically, path <I>p</I> has no more weight than the particular path that takes a shortest path from source <I>s</I> to vertex <I>u </I>and then takes edge (<I>u, v</I>).      <P>
<P>