?? chap25.htm
字號:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap26.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="chap24.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="08bd_17d1">CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS<a name="08bd_17d1"></h1><P>
<a name="08bd_17c6"><a name="08bd_17c7">A motorist wishes to find the shortest possible route from Chicago to Boston. Given a road map of the United States on which the distance between each pair of adjacent intersections is marked, how can we determine this shortest route? <P>
One possible way is to enumerate all the routes from Chicago to Boston, add up the distances on each route, and select the shortest. It is easy to see, however, that even if we disallow routes that contain cycles, there are millions of possibilities, most of which are simply not worth considering. For example, a route from Chicago to Houston to Boston is obviously a poor choice, because Houston is about a thousand miles out of the way.<P>
<a name="08bd_17c8"><a name="08bd_17c9"><a name="08bd_17ca"><a name="08bd_17cb"><a name="08bd_17cc">In this chapter and in Chapter 26, we show how to solve such problems efficiently. In a <I><B>shortest-paths problem</I></B>, we are 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"> <B>R</B> mapping edges to real-valued weights. The <I><B>weight</I></B> of path p = <img src="../images/lftwdchv.gif"><I>v<SUB>0</I></SUB>, <I>v</I><SUB>1</SUB>, . . . , <img src="../images/upsil12.gif"><I><SUB>k</I></SUB><img src="../images/wdrtchv.gif"> is the sum of the weights of its constituent edges:<P>
<img src="514_a.gif"><P>
We define the <I><B>shortest-path weight</I></B> from <I>u</I> to <I>v</I> by<P>
<img src="514_b.gif"> if there is a path from <I>u</I> to <I>v</I>, otherwise.<P>
<a name="08bd_17cd"><a name="08bd_17ce">A <I><B>shortest path</I></B><I> </I>from vertex <I>u</I> to vertex <I>v</I> is then defined as any path <I>p</I> with weight<I> w </I>(<I>p</I>)<I> = </I><img src="../images/delta12.gif"><I>(</I>u, v<I>)</I>.<P>
In the Chicago-to-Boston example, we can model the road map as a graph: vertices represent intersections, edges represent road segments between intersections, and edge weights represent road distances. Our goal is to find a shortest path from a given intersection in Chicago (say, Clark St. and Addison Ave.) to a given intersection in Boston (say, Brookline Ave. and Yawkey Way).<P>
Edge weights can be interpreted as metrics other than distances. They are often used to represent time, cost, penalties, lossage, or any other quantity that accumulates linearly along a path and that one wishes to minimize.<P>
<a name="08bd_17cf"><a name="08bd_17d0">The breadth-first-search algorithm from Section 23.2 is a shortest-paths algorithm that works on unweighted graphs, that is, graphs in which each edge can be considered to have unit weight. Because many of the concepts from breadth-first search arise in the study of shortest paths in weighted graphs, the reader is encouraged to review Section 23.2 before proceeding.<P>
<h2>Variants</h2><P>
<a name="08bf_17d1"><a name="08bf_17d2">In this chapter, we shall focus on the <I><B>single-source shortest-paths problem</I>:</B> given a graph <I>G</I> = (<I>V</I>, <I>E</I>), we want to find a shortest path from a given <I><B>source</I></B> vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I> to every vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>. Many other problems can be solved by the algorithm for the single-source problem, including the following variants.<P>
<a name="08bf_17d3"><a name="08bf_17d4"><B>Single-destination shortest-paths problem:</B> Find a shortest path to a given <I><B>destination</I></B> vertex <I>t</I> from every vertex <I>v</I>. By reversing the direction of each edge in the graph, we can reduce this problem to a single-source problem.<P>
<a name="08bf_17d5"><B>Single-pair shortest-path problem:</B> Find a shortest path from <I>u</I> to <I>v</I> for given vertices <I>u</I> and <I>v</I>. If we solve the single-source problem with source vertex <I>u</I>, we solve this problem also. Moreover, no algorithms for this problem are known that run asymptotically faster than the best single-source algorithms in the worst case.<P>
<a name="08bf_17d6"><B>All-pairs shortest-paths problem:</B> Find a shortest path from <I>u</I> to <I>v</I> for every pair of vertices <I>u</I> and <I>v.</I> This problem can be solved by running a single-source algorithm once from each vertex; but it can usually be solved faster, and its structure is of interest in its own right. Chapter 26 addresses the all-pairs problem in detail.<P>
<P>
<h2>Negative-weight edges</h2><P>
<a name="08c0_17d7"><a name="08c0_17d8"><a name="08c0_17d9"><a name="08c0_17da"><a name="08c0_17db">In some instances of the single-source shortest-paths problem, there may be edges whose weights are negative. If the graph <I>G</I> = (<I>V, E</I>) contains no negative-weight cycles reachable from the source <I>s</I>, then for all <I>v </I><img src="../images/memof12.gif"><I> V</I>, the shortest-path weight <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) remains well defined, even if it has a negative value. If there is a negative-weight cycle reachable from <I>s</I>, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest path--a lesser-weight path can always be found that follows the proposed "shortest" path and then traverses the negative-weight cycle. If there is a negative-weight cycle on some path from <I>s</I> to <I>v</I>, we define <img src="../images/delta12.gif"> <I></I>(<I>s,v</I>)<I> </I> = -<img src="../images/infin.gif">.<P>
Figure 25.1 illustrates the effect of negative weights on shortest-path weights. Because there is only one path from <I>s</I> to <I>a</I> (the path <img src="../images/lftwdchv.gif"><I>s, a</I><img src="../images/wdrtchv.gif">), <img src="../images/delta12.gif"><I></I>(<I>s, a</I> = <I>w</I>(<I>s, a</I>) = 3. Similarly, there is only one path from <I>s</I> to <I>b</I>, and so <img src="../images/delta12.gif"><I></I>(<I>s, b</I>) = <I>w</I>(<I>s, a</I>) + <I>w</I>(<I>a, b</I>) = 3 + (-4) = - 1. There are infinitely many paths from <I>s</I> to <I>c</I>: <img src="../images/lftwdchv.gif"><I>s, c</I><img src="../images/wdrtchv.gif">, <img src="../images/lftwdchv.gif"><I>s, c, d, c</I><img src="../images/wdrtchv.gif">, <img src="../images/lftwdchv.gif"><I>s, c, d, c, d, c</I><img src="../images/wdrtchv.gif">, and so on. Because the cycle <img src="../images/lftwdchv.gif"><I>c, d, c</I><img src="../images/wdrtchv.gif"> has weight 6 + (-3) = 3 > 0, the shortest path from <I>s</I> to <I>c</I> is <img src="../images/lftwdchv.gif"><I>s, c</I><img src="../images/wdrtchv.gif">, with weight <img src="../images/delta12.gif"><I></I>(<I>s, c</I>) = 5. Similarly, the shortest path from <I>s</I> to <I>d</I> is <img src="../images/lftwdchv.gif"><I>s, c, d</I><img src="../images/wdrtchv.gif">, with weight <img src="../images/delta12.gif"><I></I>(<I>s, d</I>) = <I>w</I>(<I>s, c</I>) + <I>w</I>(<I>c, d</I>) = 11. Analogously, there are infinitely many paths from <I>s</I> to <I>e</I>: <img src="../images/lftwdchv.gif"><I>s, e</I><img src="../images/wdrtchv.gif">, <img src="../images/lftwdchv.gif"><I>s, e, f, e</I><img src="../images/wdrtchv.gif">, <img src="../images/lftwdchv.gif"><I>s, e, f, e, f, e</I><img src="../images/wdrtchv.gif">, and so on. Since the cycle <img src="../images/lftwdchv.gif"><I>e, f, e</I><img src="../images/wdrtchv.gif"> has weight 3 + (-6) = -3 < 0, however, there is no shortest path from <I>s</I> to <I>e</I>. By traversing the negative-weight cycle <img src="../images/lftwdchv.gif"><I>e, f, e</I><img src="../images/wdrtchv.gif"> arbitrarily many times, we can find paths from <I>s</I> to <I>e</I> with arbitrarily large negative weights, and so <img src="../images/delta12.gif"><I></I>(<I>s, e</I>) = -<img src="../images/infin.gif">. Similarly, <img src="../images/delta12.gif"><I></I>(<I>s, f</I>) -<img src="../images/infin.gif">. Because <I>g</I> is reachable from <I>f</I>, we can also find paths with arbitrarily large negative weights from <I>s</I> to <I>g</I>, and <img src="../images/delta12.gif"><I></I>(<I>s, g</I>) = -<img src="../images/infin.gif">. Vertices <I>h, i, and j</I> also form a negative-weight cycle. They are not reachable from <I>s</I>, however, and so <img src="../images/delta12.gif"><I></I>(<I>s, h</I>) = <img src="../images/delta12.gif"><I></I>(<I>s, i</I>) = <img src="../images/delta12.gif"><I></I>(<I>s, j</I>) = <img src="../images/infin.gif">.<P>
<img src="516_a.gif"><P>
<h4><a name="08c0_17dc">Figure 25.1 Negative edge weights in a directed graph. Shown within each vertex is its shortest-path weight from source s. Because vertices e and f form a negative-weight cycle reachable from s, they have shortest-path weights of -<img src="../images/infin.gif">. Because vertex g is reachable from a vertex whose shortest-path weight is -<img src="../images/infin.gif">, it, too, has a shortest-path weight of -<img src="../images/infin.gif">. Vertices such as h, i, and j are not reachable from s, and so their shortest-path weights are <img src="../images/infin.gif">, even though they lie on a negative-weight cycle.<a name="08c0_17dc"></sub></sup></h4><P>
Some shortest-paths algorithms, such as Dijkstra's algorithm, assume that all edge weights in the input graph are nonnegative, as in the road-map example. Others, such as the Bellman-Ford algorithm, allow negative-weight edges in the input graph and produce a correct answer as long as no negative-weight cycles are reachable from the source. Typically, if there is such a negative-weight cycle, the algorithm can detect and report its existence.<P>
<P>
<h2>Representing shortest paths</h2><P>
<a name="08c1_17dc">We often wish to compute not only shortest-path weights, but the vertices on the shortest paths as well. The representation we use for shortest paths is similar to the one we used for breadth-first trees in Section 23.2. Given a graph <I>G</I> = (<I>V, E</I>), we maintain for each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I> a <I><B>predecessor</I></B><I> </I><img src="../images/piuc.gif"><I></I>[<I>v</I>] that is either another vertex or <FONT FACE="Courier New" SIZE=2>NIL</FONT>. The shortest-paths algorithms in this chapter set the <img src="../images/piuc.gif"> attributes so that the chain of predecessors originating at a vertex <I>v</I> runs backwards along a shortest path from <I>s</I> to <I>v</I>. Thus, given a vertex <I>v</I> for which <img src="../images/piuc.gif"><I></I>[<I>v</I>] <img src="../images/noteq.gif"> <FONT FACE="Courier New" SIZE=1>NIL</FONT>, the procedure <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>PATH</FONT> (<I>G</I>, <I>s, v</I>) from Section 23.2 can be used to print a shortest path from <I>s</I> to <I>v</I>.<P>
<a name="08c1_17dd">During the execution of a shortest-paths algorithm, however, the <img src="../images/piuc.gif"><I> </I>values need not indicate shortest paths. As in breadth-first search, we shall be interested in the <I><B>predecessor subgraph</I></B> <I>G</I><img src="../images/piuc.gif"><I> = (</I>V<SUB><img src="../images/piuc.gif"></SUB>, E<SUB><img src="../images/pi14.gif"></SUB>) induced by the <img src="../images/piuc.gif"><I></I> values. Here again, we define the vertex set <I>V<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"></FONT>, to be the set of vertices of <I>G</I> with non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> predecessors, plus the source <I>s</I>:<P>
<pre><I>V</I><SUB></SUB><img src="../images/piuc.gif"><SUB> = {<I>v</I> <img src="../images/memof12.gif"> <I>V</I> : <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/noteq.gif"> NIL} <img src="../images/wideu.gif"> {<I>s</I>} .</sub></sup></pre><P>
The directed edge set <I>E<FONT FACE="Courier New" SIZE=2></I><img src="../images/piuc.gif"><I></I></FONT> is the set of edges induced by the <img src="../images/piuc.gif"><I></I> values for vertices in <I>V</I><img src="../images/piuc.gif"><I><SUB></I>:<P>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -