chap26.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h2>Producing nonnegative weights by reweighting</h2><P>
Our next goal is to ensure that the second property holds: we want <img src="567_d.gif"> (<I>u, v</I>) to be nonnegative for all edges (<I>u,v</I>)<I> </I><img src="../images/memof12.gif"><I> E</I>. Given a weighted, directed graph <I>G = </I>(<I>V, E</I>) with weight function <img src="../images/omega12.gif"><I>: E</I> <img src="../images/arrow12.gif"> <B>R</B>, we make a new graph <I>G</I>'<I> = </I>(<I>V</I>'<I>, E</I>'), where <I>V</I>'<I> = V </I><img src="../images/wideu.gif"> {<I>s</I>} for some new vertex <I>s </I><img src="../images/notmem.gif"><I> V</I> and <I>E</I>'<I>= E </I><img src="../images/wideu.gif"> {(<I>s, </I><img src="../images/upsil12.gif">): <I>v</I> <img src="../images/memof12.gif"><I> V</I>}. We extend the weight function <I>w</I> so that <img src="../images/omega12.gif"><I> </I>(<I>s,v</I>) = 0 for all <I>v </I><img src="../images/memof12.gif"><I> V</I>. Note that because <I>s</I> has no edges that enter it, no shortest paths in <I>G</I>'<I>,</I> other than those with source <I>s</I>, contain <I>s</I>. Moreover, <I>G</I>'<I> </I>has no negative-weight cycles if and only if <I>G</I> has no negative-weight cycles. Figure 26.6(a) shows the graph <I>G</I>'<I> </I>corresponding to the graph <I>G</I> of Figure 26.1.<P>
Now suppose that <I>G</I> and <I>G</I>' have no negative-weight cycles. Let us define <I>h(v) =</I><img src="../images/delta12.gif"><I>(s,v)</I> for all <I>v </I><img src="../images/memof12.gif"> <I>V</I>'. By Lemma 25.3, we have <I>h(v) </I><img src="../images/lteq12.gif"><I> h(u)</I> + <img src="../images/omega12.gif"><I>(u, v)</I> for all edges <I>(u,v) </I><img src="../images/memof12.gif"><I> E</I>'. Thus, if we define the new weights <img src="567_e.gif"> according to equation (26.9), we have <img src="567_f.gif"> and the second property is satisfied. Figure 26.6(b) shows the graph <I>G</I>' from Figure 26.6(a) with reweighted edges.<P>
<P>







<h2>Computing all-pairs shortest paths</h2><P>
Johnson's algorithm to compute all-pairs shortest paths uses the Bellman-Ford algorithm (Section 25.3) and Dijkstra's algorithm (Section 25.2) as subroutines. It assumes that the edges are stored in adjacency lists. The algorithm returns the usual <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif">X<img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif"> matrix <I>D = d<SUB>ij</I>,</SUB> where <I>d<SUB>ij</SUB> = </I><img src="../images/delta12.gif"><I>(i, j)</I>, or it reports that the input graph contains a negative-weight cycle. (In order for the indices into the <I>D</I> matrix to make any sense, we assume that the vertices are numbered from 1 to <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif">.)<P>
<img src="568_a.gif"><P>
<h4><a name="08eb_1864">Figure 26.6 Johnson's all-pairs shortest-paths algorithm run on the graph of Figure 26.1. (a) The graph G' with the original weight function w. The new vertex s is black. Within each vertex v is h(v) = <img src="../images/delta12.gif">(s, v). (b) Each edge (u, v) is reweighted with weight function <img src="568_b.gif">. (c)-(g) The result of running Dijkstra's algorithm on each vertex of G using weight function <img src="568_c.gif">. In each part, the source vertex u is black. Within each vertex v are the values <img src="568_d.gif"> and <img src="../images/delta12.gif">(u, v), separated by a slash. The value d<SUB>uv</SUB> = <img src="../images/delta12.gif">(u, v) is equal to <img src="568_e.gif">.<a name="08eb_1864"></sub></sup></h4><P>
<img src="569_a.gif"><P>
<a name="08eb_185f"><a name="08eb_1860"><a name="08eb_1861">This code simply performs the actions we specified earlier. Line 1 produces <I>G</I>'<I>.</I> Line 2 runs the Bellman-Ford algorithm on <I>G</I>' with weight function <I>w</I>. If <I>G</I>' , and hence <I>G</I>, contains a negative-weight cycle, line 3 reports the problem. Lines 4-11 assume that <I>G</I>' contains no negative-weight cycles. Lines 4-5 set <I>h</I>(<I>v</I>) to the shortest-path weight <img src="../images/delta12.gif">(<I>s</I>,<I> v</I>) computed by the Bellman-Ford algorithm for all <I>v </I><img src="../images/memof12.gif"><I> V</I>'. Lines 6-7 compute the new weights <img src="569_b.gif">. For each pair of vertices <I>u, v </I><img src="../images/memof12.gif"><I> V</I>, the <B>for</B> loop of lines 8-11 computes the shortest-path weight <img src="569_c.gif"> by calling Dijkstra's algorithm once from each vertex in <I>V</I>. Line 11 stores in matrix entry <I>d<SUB>uv</I></SUB> the correct shortest-path weight <img src="../images/delta12.gif"><I>(u, v)</I>, calculated using equation (26.10). Finally, line 12 returns the completed <I>D</I> matrix. Figure 26.6 shows the execution of Johnson's algorithm.<P>
<a name="08eb_1862"><a name="08eb_1863">The running time of Johnson's algorithm is easily seen to be <I>O(V<SUP>2</SUP> </I>lg<I> V + VE)</I> if the priority queue in Dijkstra's algorithm is implemented by a Fibonacci heap. The simpler binary-heap implementation yields a running time of <I>O</I>(<I>V E </I>1g<I> V</I>), which is still asymptotically faster than the Floyd-Warshall algorithm if the graph is sparse.<P>
<P>







<h2><a name="08ec_0001">Exercises<a name="08ec_0001"></h2><P>
<a name="08ec_0002">26.3-1<a name="08ec_0002"><P>
Use Johnson's algorithm to find the shortest paths between all pairs of vertices in the graph of Figure 26.2. Show the values of <I>h</I> and <img src="569_d.gif"> computed by the algorithm.<P>
<a name="08ec_0003">26.3-2<a name="08ec_0003"><P>
What is the purpose of adding the new vertex <I>s</I> to <I>V</I>, yielding <I>V</I>'<I>?</I><P>
<a name="08ec_0004">26.3-3<a name="08ec_0004"><P>
Suppose that <I>w</I>(<I>u, v</I>) <img src="../images/gteq.gif"> 0 for all edges (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"><I> E</I>. What is the relationship between the weight functions <I>w </I>and <img src="570_a.gif"> ?<P>
<P>


<P>







<h1><a name="08ed_0001">* 26.4 A general framework for solving path problems in directed graphs<a name="08ed_0001"></h1><P>
In this section, we examine "closed semirings," an algebraic structure that yields a general framework for solving path problems in directed graphs. We start by defining closed semirings and discussing how they relate to a calculus of directed paths. We then show some examples of closed semirings and a "generic" algorithm for computing all-pairs path information. Both the Floyd-Warshall algorithm and the transitive-closure algorithm from Section 26.2 are instantiations of this generic algorithm.<P>





<h2>Definition of closed semirings</h2><P>
<a name="08ee_1864"><a name="08ee_1865"><a name="08ee_1866"><a name="08ee_1867"><a name="08ee_1868"><a name="08ee_1869"><a name="08ee_186a"><a name="08ee_186b"><a name="08ee_186c"><a name="08ee_186d"><a name="08ee_186e"><a name="08ee_186f">A<I> <B>closed semiring</I></B> is a system <img src="570_b.gif"> where <I>S</I> is a set of elements, <img src="../images/xor14.gif"> (the <I><B>summary operator</I></B>) and <img src="570_c.gif"> (the <I><B>extension operator)</I></B> are binary operations on <I>S</I>, and <img src="570_d.gif"> are elements of <I>S</I>, satisfying the following eight properties:<P>
1.     <img src="570_e.gif"> is a <I><B>monoid</I></B><I>:</I><P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     <I>S </I></FONT>is <I><B>closed</I></B> under <img src="../images/xor14.gif">: <I>a</I> <img src="../images/xor14.gif"> b <img src="../images/memof12.gif"> <I>S</I> for all <I>a, b</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     <img src="../images/xor14.gif"></FONT> is <I><B>associative</I>:</B><I> a</I> <img src="../images/xor14.gif"> (<I>b </I><img src="../images/xor14.gif"> <I>c</I>) = (<I>a</I> <img src="../images/xor14.gif"><I> b</I>) <img src="../images/xor14.gif"> <I>c </I>for all <I>a</I>,<I>b</I>,<I>c</I> <img src="../images/memof12.gif"> <I>S.</I><P>
<img src="570_f.gif"><P>
Likewise, <img src="570_g.gif"> is a monoid.<P>
<img src="570_h.gif"><P>
3.     <img src="../images/xor14.gif"> is <I><B>commutative:</I></B><I> a </I><img src="../images/xor14.gif"> <I>b</I> = <I>b</I> <img src="../images/xor14.gif"> <I>a</I> for all <I>a</I>, <I>b</I> <img src="../images/memof12.gif"> <I>S.</I><P>
4.     <img src="../images/xor14.gif"> is <I><B>idempotent:</I></B><I> a </I><img src="../images/xor14.gif"> <I>a</I> = <I>a</I> for all <I>a</I> <img src="../images/memof12.gif"> <I>S.</I><P>
<img src="570_i.gif"><P>
6.     If <I>a</I><SUB>1</SUB>,<I> a</I><SUB>2</SUB>,<I> a</I><SUB>3</SUB>, . . . is a countable sequence of elements of <I>S</I>, then <I>a</I><SUB>1</SUB> <img src="../images/xor14.gif"> <I>a</I><SUB>2</SUB> <img src="../images/xor14.gif"> <I>a</I><SUB>3</SUB> <img src="../images/xor14.gif"> . . . is well defined and in <I>S</I>.<P>
7.     Associativity, commutativity, and idempotence apply to infinite summaries. (Thus, any infinite summary can be rewritten as an infinite summary in which each term of the summary is included just once and the order of evaluation is arbitrary.)<P>
<img src="570_j.gif"><P>
<P>







<h2>A calculus of paths in directed graphs</h2><P>
<a name="08ef_1870"><a name="08ef_1871"><a name="08ef_1872"><a name="08ef_1873"><a name="08ef_1874">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 <I>G = </I>(<I>V, E</I>) and a <I><B>labeling function</I></B> <img src="../images/lambdauc.gif">: <I>V </I>X<I> V </I><img src="../images/arrow12.gif"><I> S</I> mapping all ordered pairs of vertices into some codomain <I>S</I>.The <I><B>label of edge</I></B> (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"><I> E</I> is denoted ,<img src="../images/lambdauc.gif">(<I>u, v</I>). Since <img src="../images/lambdauc.gif"> is defined over the domain <I>V </I>X<I> V,</I> the label <img src="../images/lambdauc.gif">(<I>u, v</I>) is usually taken as <img src="571_a.gif"> if (<I>u, v</I>) is not an edge of <I>G</I> (we shall see why in a moment).<P>
<a name="08ef_1875">We use the associative extension operator <img src="571_b.gif"> to extend the notion of labels to paths. The <I><B>label of path</I></B> <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><SUB> </I></SUB>is<P>
<img src="571_c.gif"><P>
The identity <img src="571_d.gif"> serves as the label of the empty path.<P>
As a runing example of an application of closed semirings, we shall use shortest paths with nonnegative edge weights. The codomain <I>S i</I>s <B>R</B><img src="../images/gteq.gif"><SUP>0</SUP> <img src="../images/wideu.gif"> {<FONT FACE="Times New Roman" SIZE=3><img src="../images/infin.gif"></FONT>}, where <B>R</B><img src="../images/gteq.gif"><SUP>0</SUP> is the set of nonnegative reals, and <img src="../images/lambdauc.gif"><I>(i, j) = w<SUB>ij</I></SUB> for all <I>i, j </I><img src="../images/memof12.gif"><I> V</I>. The extension operator <img src="571_e.gif"> corresponds to the arithmetic operator +, and the label of path <I>p =</I><img src="../images/lftwdchv.gif"><I>v<SUB>1</SUB>,v<SUB>2</I>, . . . ,</SUB><I>v<SUB>k</I></SUB><img src="../images/wdrtchv.gif"><I> </I>is therefore<P>
<img src="571_f.gif"><P>
Not surprisingly, the role of <img src="751_g.gif"> , the identity for <img src="571_h.gif"> , is taken by 0, the identity for +. We denote the empty path by <img src="../images/epsilon.gif">, and its label is <img src="571_i.gif">.<P>
<a name="08ef_1876"><a name="08ef_1877">Because the extension operator <img src="571_j.gif"> is associative, we can define the label of the concatenation of two paths in a natural way. Given paths <I>p</I><SUB>1</SUB> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>1</SUB><I>,v</I><SUB>2</SUB><I>, . . . ,v<SUB>k</SUB></I><img src="../images/wdrtchv.gif"><I> </I>and<I> p</I><SUB>2<I> = </I></SUB><img src="../images/lftwdchv.gif"><I><SUB>vk</SUB>,v<SUB>k+</I>, . . . ,</SUB><I>,v</I><SUB>1</SUB><img src="../images/wdrtchv.gif"><I>, </I>their <I><B>concatenation</I></B> is<P>
<pre><I>p</I><SUB>1</SUB> <SUB><img src="../images/degree.gif"></SUB> <I>p</I><SUB>2</SUB> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>, . . . ,<I>v<SUB>k</I></SUB>,<I>v<SUB>k</I>+1</SUB>, . . . ,<I>v<SUB>l</I></SUB><img src="../