最短路径文献翻译终极版

单位代码01学号*********分类号O24密级文献翻译最短通路问题院(系)名称信息工程学院专业名称信息与计算科学学生姓名许秀成指导教师孙贵玲2013年 3 月10日8. 6 最短通路问题8.6.1引言许多问题可以用边上赋权的图来建模。

考虑一下航线系统如何建模。

如果用顶点表示城市，用边表示航线。

给边赋上城市之间的距离，就可以为涉及距离的问题建模；给边赋上飞行时间，就可以为涉及飞行时间的问题建模；给边赋上票价，就可以为涉及票价的问题建模。

图8—61显示了给一个图的边赋权的三种不同方式，分别表示距离，飞行时间和票价。

波士顿波士顿 密图 8-61 为航线系统建模的带权图给每条边赋上一个数的图称为带权图。

带权图用来为计算机网络建模。

通信成本（比如租用电话线的月租费）、计算机在这些线路上的响应时间或是计算机之间的距离等都可以用带权图来研究。

图8—62显示一些带权图，它们表示给计算机的图的边赋权的三种方式，分别对应成本、响应时间和距离。

与带权图有关的几种类型的问题出现得很多。

确定网络里两个顶点之间长度最短的通路就是一个这样的问题。

说的更具体些，设带权图里一条通路的长度是这条通路上各边的权的总和。

（读者应当注意，对术语长度的这种用法，与表示不带权的图的通路里边数的长度的用法，这两者是不同的。

）问题是：什么是最短通路，即什么是在两个给定顶点之间长度最短的通路?例如，在图8—61所示带权图表示的航线系统里，在波士顿与洛杉矶之间以空中距离计算的最短通路是什么？在波士顿与洛杉矶之间什么样的航班组合的总飞行时间（即在空中的总时间，不包括航班之间的时间）最短？在这两个城市之间的最低费用是多少？波士顿距离达拉斯图 8-62 为计算机网络建模的带权图在图8—62所示的计算机网络里，连接旧金山的计算机与纽约的计算机所需要的最便宜的一组电话线是什么？哪一组电话线给出旧金山与纽约之间的通信的最短响应时间？哪一组电话线有最短的总距离？与带权图有关的另外的一个重要问题是：求访问完全图每个顶点恰好一次的、总长度最短的回路。

这就是著名的旅行商问题，它求一位推销商应当以什么样的顺序来访问其路程上的每个城市恰好一次，使得他旅行的总距离最短。

本节后面将讨论旅行商问题。

8.6.2 最短通路算法求带权图里两个顶点之间的最短通路有几个不同的算法。

下面将给出荷兰数学家E ·迪克斯特拉在1959年所发现的一个解决无向带权图中最短通路问题的算法，其中所有的权都是正数。

可以很容易地将它修改后来解决有向图里的最短通路问题。

响应时间达拉斯秒月租费达拉斯在给出这个算法的形式化表示之前将给出一个启发性的例子。

例 1 在图8—63所示的带权图里，a 和z 之间的最短通路的长度是多少？图 8—63解 虽然通过观察就容易求出最短通路，但是需要想出一些有助于理解迪克施特拉算法的办法。

要解决的问题就是：求从a 到各个相继的顶点的最短通路，直到到达z 为止。

从a 开始、（直到到达终点为止）不包括除a 以外的顶点的唯一通路是a ,b 和a ,d 。

因为a ,b 和a ，d 的长度分别是4和2，所以d 是与a 最近的顶点。

可以通过查看（直到到达终点为止）只经过a 和d 的所有通路，来求出下一个最靠近a 的顶点。

到b 的最短通路仍然是a ，b ，长度为4，而到e 的最短通路是a ,e d ,，长度为5。

所以，下一个与a 最靠近的顶点是b 。

为了找出第三个与a 最近的顶点，只需要检查（直到到达终点为止）只经过了d a ,和b 的那些通路。

存在长度为7到c 的通路，即c b a ,,,以及长度为6到z 的通路，即z ed a ,,,。

所以，z 是下一个与a 最靠近的顶点，而且到z 的最短通路的长度为6。

例 1 说明了在迪克斯特拉算法里使用的一般原理。

注意通过检查就可能求出从a 到z 最短通路。

不过，无论对人还是对计算机来说，检查边数很多的图都是不切实际的。

现在将考虑一般问题：在无向联通简单带权图里，求出a 与z 之间的最短通路的长度。

迪克斯特拉算法如下进行：求出从a 到第一个顶点的最短通路的长度，从a 到第二个顶点最短通路的长度，以此类推，直到求出a 到z 的最短通路长度为止。

这个算法依赖于一系列的迭代。

通过在每次跌代里添加一个顶点来构造出特殊顶点的集合。

在每次跌代里完成一个标记过程。

在这个标记过程，只包括特殊顶点的从a 到w 的最短通路的长度来标记w 。

添加到特殊顶点集里的顶点是尚在集合之外的那些顶点az中带有最小标记的顶点。

现在给出迪克斯特拉算法的细节。

它首先用0标记a 而用∞标记其余的顶点。

用记号0)(0=a L 和∞=)(0v L 表示在没有发生任何迭代之前的这些标记（下标0表示“第0次”迭代)。

这些标记是从a 到这些顶点的最短通路的长度，其中这些通路只包含顶点a 。

（因为不存在a 到其他顶点的这种通路，所以∞是a 与这样的顶点之间的最短通路的长度。

）迪克斯特拉算法是通过形成特殊顶点的集合来进行的。

设k s 表示在标记过程k 次迭代之后的特殊顶点集。

首先φ=0S 。

集合k s 是通过过程把不属于1-k s 的带最小标记的顶点u 添加到1-k s 里形成的，一旦把u 添加到k s 里，就更新所有不属于k s 的顶点的标记，使得顶点v 在第个阶段的标记k L ()v 是只包含k s 里顶点(即已有的特殊点再加上u ）的、从a 到v 的最短通路的长度。

设v 是不属于k s 的一个顶点。

为了更新v 的标记，注意k L ()v 是只包含k s 里k 顶点的从a 到v 的最短通路，要么是只包含1-k s 里顶点（即不包括u 在内的特殊顶点）的从a 到v 的最短通路，要么1-k 阶段加上边（v u ,）的从a 到u 的最短通路。

换句话说，(){()()()}v u w u a L v a L v a L k k ,,,,m in ,11+=--这个过程这样迭代：相继添加顶点到特殊顶点集里，直到添加z 为止。

当把z 添加到特殊顶点集里时，它的标记就是从a 到z 的最短通路的长度。

在算法1里给出迪克斯特拉算法。

随后将证明这个算法的正确性。

算法1 迪克施特拉算法Procedure Dijkkstra(G :所有权都为正数的带权连通简单图）{G 带有顶点z v v a ==,...1,0和权)(,j i v v w ，其中若},{j i v v 不是G 里的边，则)(,j i v v w =∞} For i:=1 to n)(i v L :=∞)(a L :=0 S ：=φ{ 现在初始化标记，使得a 的标记为0而所有其余标记为∞，S 是空集合 } While z ∉S Beginu :=不属于S 的)(u L 最小的一个顶点S ：=S }{uFor 所有不属于S 的顶点vIf )(u L ),(v u w +)(v L < then ),()(:)(v u w u L v L +={这样就给S 里添加带最小标记的顶点，而且更新不在S 里的顶点的标记} end =)({z L 从a 到z 的最短通路的长度}下面的例子说明迪克施特拉算法是如何工作的。

随后我们将证明这个算法总是产生带权图里两个顶点之间最短通路的长度。

例 2 用迪克施特拉算法求图8—64a 所示的带权图里顶点a 与z 之间最短通路的长度。

解 图8—64里显示了迪克斯特拉算法求a 与z 之间最短通路所用的步骤。

在算法的每次迭代里，用圆圈圈起集合k S 里的顶点。

对每次迭代都标明了只包含k S 里顶点的从a 到每个顶点的最短通路。

当圆圈圈到z 时，算法终止。

找到从a 到z 的最短通路是e d b c a ,,,,,长度为13。

下一步，用归纳论证来证明迪克斯特拉算法产生无向连通带权图里两个顶点a 与z 之间最短通路的长度。

用下列断言作为归纳假设:在第k 次迭代里 )(i S 里的顶点v )0(≠v 的标记是从a 到这个顶点的最短通路的长度。

)(ii 不在S 里的顶点的标记是（这个顶点自身除外）只包含S 里顶点的最短通路的长度。

当0=k 时，在没有执行任何迭代之前，}{a S =，所以从a 到除a 外的顶点的最短通路长度是∞。

设v 是第1+k 次迭代里添加到S 里的顶点，使得v 是在第k 次迭代结束时带最小标记的不在S 里的顶点不唯一的情形里，可以采用带最小标记的任意顶点。

根据归纳假设，可以看出在第1+k 次迭代之前，S 里的顶点都用从a 出发的最短通路的长度来标记。

图8-64 用迪克斯特拉算法求从a 到z 的最短距离另外，必须用从a 到v 的最短通路的长度来标记v 。

假如情况不是这样，那么在第k 次迭代结束时，就可能存在包含不在S 里的顶点的、长度小于)(v L k 的通路（因为)(v L k 是在第k 次迭代之后、只包含S 里顶点的、从a 到v 的最短通路的长度）。

设u 是在这样的通路里不属于S 的第一个顶点。

则存在一条只包含S 里顶点的、从a 到u 的长度小于)(v L k 的通路。

这与对v 的选择相矛盾。

因此，在第1+k 次迭代时)(i 成立。

设u 是在第1+k 次迭代之后不属于S 的一个顶点。

只包含S 里顶点的从a 到u 的最短通路要么包含v 、要么不包含v 。

若它不包含v ，则根据归纳假设，它的长度是)(u L k 。

若它确实包含v ，则它必然是这样组成的：一条只包含S 里除v 之外的顶点的、从a 到v 具有最短可能长度的通路，后面接着从v 到u 的边。

这种情形里它的长度是),()(u v w v L k +。

这样就证明了)(ii 为真，因为)},(min{)()(),(1u v w L L u L v k u k k +=+。

已经证明了定理1.定理1 迪克斯特拉算法求出连通简单无向带权图里两个顶点之间最短通路的长度。

现在可以估计迪克斯特拉算法的计算复杂性（就加法和比较而言）。

这个算法使用的迭代次数不超过n -1次，因为在每次迭代里添加一个顶点到特殊顶点集里。

若可以估计每次迭代所使用的运算次数，则大功告成。

可以用不超过n -1次比较来找出不在k S 里的带最小标记的顶点。

于是我们使用一次加法和一次比较来更新不在k S 中的每一个顶点的标记，所以在每次迭代里的运算不超过)1(2-n 次，因为在每次迭代里要更新的标记不超过n -1个。

因为迭代次数不超过n -1次，每次迭代的运算次数不超过)1(2-n ，所以有下面的定理。

定理 2 迪克斯特拉算法使用)(2n O 次运算（加法和比较）来求出连通简单无向带权图里两个顶点之间最短通路的长度。

来源于：罗森(美)．离散数学及其应用．北京：机械工业出版社，2003．8(6)：491-496．附:英文原文8.6 Shortest-Path Problems8.6.1 IntroductionMany problems can be modeled using graphs with weights assigned to their edges. As an illustration, consider how an airline system can be modeled. We set up the basic graph model by representing cities by vertices and flights by edges. Problems involving flight time can be modeled by assigning flight times to edges. Problems involving fares can be modeled by assigning fares to the edges. Figure 1 displays three different assignments of weights to the edges of a graph representing distances, flight times, and fares, respectively.Graphs that have a number assigned to each are called weighted graphs. Weighted graphs are used to model computer networks. Communications costs (such as the monthly cost of leasing a telephone line),the response times of the computers over these lines, or the distance between computer, can all be studied using weighted graphs, Figure 2 display weighted graphs that represent three ways to assign weights to the edges of a computer network, corresponding to distance, response time, and cost.Several types of problems involving weighted graphs arise frequently. Determining a path of least length between two vertices in a network is one such problem. To be more specific, let the length of a path in a weighted graph be the sum of the weights of the edges of this path.(The reader should note that this use of the term length is different from the use of length to denote the number of edges in a path in a graph without weights.)BostonThe question is: What is a shortest path, that is, a path of least length, between two given vertices? For instance, in the airline system represented by the weighted graph shown in Figure 1, what is a shortest path in air distance between Boston and Los Angles? What combinations of flights has the smallest total flight time (that is, total time in the air, not including time between flights) between Boston and Los Angels? What is the cheapest fare between these two cities? In the computer network shown in 2, what is a least expensive set of telephone lines gives a fastest response time for communications between San Francisco and New York? Which set of lines has a shortest overall distance?There are several different algorithms that find a shortest path between two vertices in a weighted graph. We will present an algorithm discovered by the Dutch mathematician Edger Dijkstra in 1959. The version we will describe solves this problem in undirected weighted graphs where all the weights are positive. It is easy to adapt it to solve shortest-path problems in directed graphs.BostonFIGURE 8-61 Weighted Graphs Modeling an Airline SystemAnother important problems involving weighted graphs asks for a lot of shortest totallength that visits every vertex of a complete graph exactly once. This is the famous traveling salesman problem,which asks for an order in which a salesman should visit each of the citieson his route exactly once so that he travels the minimum total distance. We will discuss the on traveling salesman problem later in this section.DISTANCEDallasRESPONSE TIMEDallasLEASE RATES(PER MONTH)DallasFIGURE 2 Weighted Graphs Modeling a Computer Network8.6.2 A Shortest-Path AlgorithmThere are several different algorithms that find a shortest path between two vertices in a weighted graph. We will present an algorithm discovered by the Dutch mathematician Edger Dijkstra in 1959. The version we will describe solves this problem in undirected weighted graphs where all the weights are positive. It is easy to adapt it to solve shortest-path problems in directed graphs.Before giving a formal presentation of the algorithm, we will give a motivating example. EXAMPLE 1What is the length of a shortest path between a and z in the weighted graph shown in Figure 3?FIGHER 8-63Solution: Although a shortest path is easily found by inspection , we will develop some ideas useful in understanding Dijkstra’s algorithm. We will solve this problem by finding the length of a shortest path from a to successive vertices, until z is reached.The only paths starting at a that contain no vertex other than a (until the terminal vertex is reached) are b a , and d a ,. Because the lengths of b a , and d a , are 4 and 2, respectively, it follows that d is the closest vertex to a .We can find the next closest vertex by looking at all paths that go through only a andd (until the terminal vertex is reached). The shortest such path to b is still b a ,, with length4,and the shortest such path to e is e d a ,,, with length 5.Consequently, the next closest vertex to a is b .To find the third closest vertex to a , we need to examine only paths that go through onlyd a , and b (until the terminal vertex is reached). There is a path of length 7 to c namelyc b a ,, and a path of length 6 to z , namely,ze d a ,,,. Consequently, z is the next closestvertex to a , and the length of a shortest path to z is 6.Example 1 illustrates the general principles used in Dijkstra’s algorithm. Note that ashortest path from a to z could have been found by inspection. However, inspection is impractical for both humans and computers for graphs with large numbers of edges.We will now consider the general problem of finding the length of a shortest path between a and z in an undirected connected simple weighed graph. Dijkstra’s algorithm proceeds by finding the length of a shortest path from a to a first vertex, the length ofaa zshortest path from a to a second vertex, and so on, until the length of a shortest from a toz is found.The algorithm relies on a series of iterations. A distinguished set of vertices is constructed by adding one vertex. A labeling procedure is carried out at earth iteration. In this labeling procedure, a vertex w is labeled with the length of a shortest path from a to w that contains only vertics already in the distinguished set. The vertex added to the distinguished set is one with a minimal label among those vertices not already in the set. We now give the details of Dijkstra’s algorithm. It begins by labeling a with 0 and the other vertices with ∞.We used the notation =)(0a L 0 and =)(0v L ∞ for these labels before any iterations have taken place (the subscript 0 stands for th e “0th” iteration). These labels are the lengths of shortest paths from a to the vertices, where the paths contain only the vertexa .(Because no path from a to a vertex different from a exists,∞ is the length of a shortest path between a and this vertex.)Dijkstra’s algorithm proceeds by forming a dist inguished set of vertices. Let k S denote this set after k iterations of the labeling procedure. We begin with =0S φ. The set k S is formed from 1-k S by adding a vertex u not in 1-k S with the smallest label. Once u is added to k S , we update the labels of all vertices not in k S , so that )(v L k ,the label of the vertex v at the kth stage, is the length of a shortest path from a to v that contains vertices only in k S (that is, vertices that were already in the distinguished set together withu ).Let v be a vertex not in k S . To update the label of v , note that )(v L k is the length of a shortest path from a to v containing only vertices in k S . The updating can be carried out efficiently when this observation is used: A shortest path from a to v containing only elements of k S is either a shortest path from a to v that contains only elements of1-k S (that is, the distinguished vertices not including u ), or it is a shortest path from a to uat the )1(-k st stage with the edge ),(v u added. In other words,(){()()()}v u w u a L v a L v a L k k ,,,,m in ,11+=--This procedure is iterated by successively, adding vertices to the distinguished set until z is added. When z is added to the distinguished set, its label is the length of a shortest path from a to z .Dijkstra’s algorithm is given in Algorithm 1. Later we will a proof that this algorithm is correct.ALGORITHM 1 Dijkstra’s Algorithm.Procedure Dijkkstra(G :weighted connected simple graph, with all weights positive)） {G has vertices z v v a ==,...1,0 and weighted )(,j i v v w ，where },{j i v v =∞ if )(,j i v v w is not an edge in G } For i:=1 to n)(i v L :=∞)(a L :=0 S ：=φ{ the label are now initialized so that the label of a is 0 and all other labels are ∞,and S is the empty set } While z ∉S Beginu :=a vertex not in S with )(u L minimalS ：=S }{uFor all vertices v not in SIf )(u L ),(v u w +)(v L < then ),()(:)(v u w u L v L +={this adds a vertex to S with minimal label and update the labels a vertices not in S }FIGURE 4 Using Dijkstra’s Algorithm to Find a Shortest Path from a to z illustrates how Dijkstra’s algorithm works. Afterwards, we will show that this algorithm always produces the length of a shortest path between two vertices in a weighted graph. EXAMPLE 2Use Dijkstra’s algorithm to find the length of a shortest path between the vertices a and z in the weighted graph displayed in Figure 4(a).Solution: The steps used by Dijkstra’s algorithm to find a shortest path between a and z are shown in Figure 4.Ateach iteration of the algorithm the vertices of the setS are circled.kA shortest path from a to each vertex containing only vertices inS is indicated for eachkiteration. The algorithm terminations when z is circled. We find that a shortest path from a to z is za,,,,,with length 13.cedbRemark: In performing Dijkstra’s algorithm it is sometimes more convenient to keep track of labels of vertices in each step using a table instead of rewarding the graph for each step.Next, we use an inductive arg ument to show that Dijkstra’s algorithm produces the length of a shortest path between two vertices a and z in an undirected connected weightedgraph. Take as the induction hypothesis the following assertion: At the k th teration. )(i the label of every vertex v in S is the length of a shortest path from a to this vertex ,and)(ii the label of every vertex note in S is the length of a shortest path from a to this vertex that contain only(besides the vertex itself) vertices in S .When 0=k , before any iterations are carried out,=S φ, so the length of a shortest path froma to a vertex other than a is ∞.Hence, the basis, case is true.Assume that the inductive hypothesis holds for the k th iteration. Let v be the vertex added to S at the )1(+k st iteration, so v is a vertex not in S at the end of the k th iteration with the smallest label (in the case of ties, any vertex with smaller label may be used).From the inductive hypothesis we see that vertices in S before (1+k )st iteration are labeled with the length of a shortest path from a .Also, v must be labeled with the length of a shortest path to it from a . If this were not the case, at the end of the kth iteration there would be a path of length less than )()(v L k is the length of a shortest path from a to v containing only vertices in S after the kth iteration. Let u be the first vertex not in S in such a path. There is a path with length less than )()(v L k from a to u containing only vertices of S . This contradicts the choice of v . Hence,)(i holds at the end of the )1(+k st iteration.Let u be a vertex not in S after 1+k iterations. A shortest path from a to u containing only elements of S either contains v or it does not. If it does not contain v , then by the inductive hypothesis its length is )()(u L k .If it does contain v ,then it must be made up of a path from a to v of shortest possible length containing elements of S other than v , followed by the edge from v to u . In this case, its length would be ),()(u v w v L k +. This shows that )(ii is true, because ),()(),(m in{)(1u v w v L u L u L k k k +=+}.Theorem 1 has been proved.THEOREM 1 Dijkstra’s algorithm finds the length of a shortest path between two vertices in a connected simple undirected weighted graph.We can now estimate the computational co mplexity of Dijkstra’s algorithm( in terms of additions and comparisons).The algorithm used no more 1-n iterations, because one vertex is added to the distinguished set at each iteration.We are done if we can estimate the number of operations used for each iteration. We can identify the vertex not in k S with the smallest label using no more than 1-n comparisons. Then we can an addition and a comparison to update the label of each vertex not in k S .It follows that no more than )1(2-n operation are used at each iteration, because there are no more than 1-n labels to update at each iteration. Because we use no more than 1-n iterations, each using no more than ()12-n operations, we have Theorem 2.THEOREM 2 Dijk stra’s algorithm use )(2n O operations (additions and comparisons) to find the length of a shortest path between two vertices in a connected simple undirected graph with n verticces.From: Kenneth H. Rosen. Discrete Mathematics and Its Applications. Beijing: China Machine Press, 2003. 8(6): 647-653。