《最短路径文献翻译终极版》由会员分享，可在线阅读，更多相关《最短路径文献翻译终极版（19页珍藏版）》请在金锄头文库上搜索。
1、单位代码 学 号 分类号 O24密 级文献翻译最短通路问题UJ院（系）名称信息工程学院专业名称信息与计算科学学生姓名许秀成指导教师孙贵玲8. 6最短通路问题8.6.1引言许多问题可以用边上赋权的图来建模。考虑一下航线系统如何建模。如果用顶点表示城市，用边表示航线。给边赋上城市之间的距离，就可以为涉及距离的问题建模；给 边赋上飞行时间，就可以为涉及飞行时间的问题建模；给边赋上票价，就可以为涉及票 价的问题建模。图861显示了给一个图的边赋权的三种不同方式，分别表示距离，飞 行时间和票价。给每条边赋上一个数的图称为带权图。带权图用来为计算机网络建模。通信成本（比 如租用电话线的月租费）、计算机在这
2、些线路上的响应时间或是计算机之间的距离等都 可以用带权图来研究。图862显示一些带权图，它们表示给计算机的图的边赋权的三 种方式，分别对应成本、响应时间和距离。与带权图有关的几种类型的问题出现得很多。确定网络里两个顶点之间长度最短的 通路就是一个这样的问题。说的更具体些，设带权图里一条通路的长度是这条通路上各 边的权的总和。（读者应当注意，对术语长度的这种用法，与表示不带权的图的通路里 边数的长度的用法，这两者是不同的。）问题是：什么是最短通路，即什么是在两个给 定顶点之间长度最短的通路?例如，在图861所示带权图表示的航线系统里，在波士 顿与洛杉矶之间以空中距离计算的最短通路是什么？在波士顿
3、与洛杉矶之间什么样的 航班组合的总飞行时间（即在空中的总时间，不包括航班之间的时间）最短？在这两个 城市之间的最低费用是多少？图8-62为计算机网络建模的带权图在图862所示的计算机网络里，连接旧金山的计算机与纽约的计算机所需要的最 便宜的一组电话线是什么？哪一组电话线给出旧金山与纽约之间的通信的最短响应时 间？哪一组电话线有最短的总距离？与带权图有关的另外的一个重要问题是：求访问完全图每个顶点恰好一次的、总长 度最短的回路。这就是著名的旅行商问题，它求一位推销商应当以什么样的顺序来访问 其路程上的每个城市恰好一次，使得他旅行的总距离最短。本节后面将讨论旅行商问题。 8.6.2最短通路算法求带
4、权图里两个顶点之间的最短通路有几个不同的算法。下面将给出荷兰数学家 E 迪克斯特拉在1959年所发现的一个解决无向带权图中最短通路问题的算法，其中所 有的权都是正数。可以很容易地将它修改后来解决有向图里的最短通路问题。在给出这个算法的形式化表示之前将给出一个启发性的例子。例1在图8-63所示的带权图里，a和乙之间的最短通路的长度是多少?解虽然通过观察就容易求出最短通路，但是需要想出一些有助于理解迪克施特拉 算法的办法。要解决的问题就是：求从a到各个相继的顶点的最短通路，直到到达z为 止。从a开始、（直到到达终点为止）不包括除a以外的顶点的唯一通路是a ,b和a, d。 因为a, b和a , d
5、的长度分别是4和2,所以d是与a最近的顶点。可以通过查看（直到到达终点为止）只经过a和d的所有通路，来求出下一个最靠 近a的顶点。到b的最短通路仍然是a，b，长度为4,而到e的最短通路是a, d, e，长 度为5。所以，下一个与a最靠近的顶点是b。为了找出第三个与a最近的顶点，只需要检查（直到到达终点为止）只经过了 a,d和b的那些通路。存在长度为7到c的通路，即a,b,c ,以及长度为6到z的通路，即a,d,e,z。 所以，z是下一个与a最靠近的顶点，而且到z的最短通路的长度为6。例1说明了在迪克斯特拉算法里使用的一般原理。注意通过检查就可能求出从a 到z最短通路。不过，无论对人还是对计算机
6、来说，检查边数很多的图都是不切实际的。现在将考虑一般问题：在无向联通简单带权图里，求出a与z之间的最短通路的长 度。迪克斯特拉算法如下进行：求出从a到第一个顶点的最短通路的长度，从a到第二 个顶点最短通路的长度，以此类推，直到求出a到z的最短通路长度为止。这个算法依赖于一系列的迭代。通过在每次跌代里添加一个顶点来构造出特殊顶点 的集合。在每次跌代里完成一个标记过程。在这个标记过程，只包括特殊顶点的从a到 的最短通路的长度来标记w。添加到特殊顶点集里的顶点是尚在集合之外的那些顶点中带有最小标记的顶点。现在给出迪克斯特拉算法的细节。它首先用0标记而用8标记其余的顶点。用记 号L0（a） = 0和L
7、0（v） = 8表示在没有发生任何迭代之前的这些标记（下标0表示“第0 次”迭代）。这些标记是从a到这些顶点的最短通路的长度，其中这些通路只包含顶点a。（因为不存在a到其他顶点的这种通路，所以8是a与这样的顶点之间的最短通路的长 度。）迪克斯特拉算法是通过形成特殊顶点的集合来进行的。设Sk表示在标记过程k次迭 代之后的特殊顶点集。首先s0 m。集合sk是通过过程把不属于%_1的带最小标记的 顶点u添加到Sk_1里形成的，一旦把u添加到七里，就更新所有不属于Sk的顶点的标 记，使得顶点v在第个阶段的标记匕（v）是只包含Sk里顶点（即已有的特殊点再加上u ） 的、从a到v的最短通路的长度。设v是不
8、属于S的一个顶点。为了更新v的标记，注意Lk （v）是只包含七 里k顶点 的从a到v的最短通路，要么是只包含Sk_里顶点（即不包括u在内的特殊顶点）的从a 到v的最短通路，要么k -1阶段加上边（u, v ）的从a到u的最短通路。换句话说，L(a, v )=min l (a, v) L (a, u)+ w(u, v) 这个过程这样迭代：相继添加顶点到特殊顶点集里，直到添加z为止。当把z添加到特 殊顶点集里时，它的标记就是从a到z的最短通路的长度。在算法1里给出迪克斯特拉 算法。随后将证明这个算法的正确性。算法1迪克施特拉算法Procedure Dijkkstra（G :所有权都为正数的带权连通
9、简单图） G带有顶点a = v v ,. = z和权w(v v )，其中若v ,v 不是G里的边，则w(v v ) =s 0, 1i, ji ji, jFor i:=1 to nL(v ) :=siL (a) :=0(现在初始化标记，使得的标记为0而所有其余标记为U S是空集合While z 史 SBeginu :=不属于S的L(u)最小的一个顶点S : = S uFor所有不属于S的顶点vIf L(u) + w(u, v) L(v) then L(v) := L(u) + w(u, v)这样就给S里添加带最小标记的顶点，而且更新不在S里的顶点的标记end L(z)=从a到z的最短通路的长度下
10、面的例子说明迪克施特拉算法是如何工作的。随后我们将证明这个算法总是产生 带权图里两个顶点之间最短通路的长度。例2用迪克施特拉算法求图864a所示的带权图里顶点a与z之间最短通路的长 度。解 图864里显示了迪克斯特拉算法求a与z之间最短通路所用的步骤。在算法的 每次迭代里，用圆圈圈起集合S*里的顶点。对每次迭代都标明了只包含S*里顶点的从a 到每个顶点的最短通路。当圆圈圈到z时，算法终止。找到从a到z的最短通路是 a, c, b, d, e,长度为 13。下一步，用归纳论证来证明迪克斯特拉算法产生无向连通带权图里两个顶点a与z 之间最短通路的长度。用下列断言作为归纳假设:在第k次迭代里S里的顶
11、点v (v主0)的标记是从a到这个顶点的最短通路的长度。(ii)不在S里的顶点的标记是(这个顶点自身除外)只包含S里顶点的最短通路的 长度。当k = 0时，在没有执行任何迭代之前，S = a，所以从a到除a外的顶点的最短通 路长度是8。设v是第k +1次迭代里添加到S里的顶点，使得v是在第k次迭代结束时 带最小标记的不在S里的顶点不唯一的情形里，可以采用带最小标记的任意顶点。根据归纳假设，可以看出在第k +1次迭代之前，S里的顶点都用从a出发的最短通图8-64用迪克斯特拉算法求从a至Ijz的最短距离另外，必须用从a到v的最短通路的长度来标记v。假如情况不是这样，那么在第化 次迭代结束时，就可能
12、存在包含不在S里的顶点的、长度小于匕(v)的通路(因为匕(v)是 在第k次迭代之后、只包含S里顶点的、从a到v的最短通路的长度)。设u是在这样的 通路里不属于S的第一个顶点。则存在一条只包含S里顶点的、从a到u的长度小于 L(v)的通路。这与对v的选择相矛盾。因此，在第k + 1次迭代时成立。设u是在第k +1次迭代之后不属于S的一个顶点。只包含S里顶点的从a到u的最 短通路要么包含v、要么不包含v。若它不包含v，则根据归纳假设，它的长度是匕(u)。 若它确实包含v，则它必然是这样组成的：一条只包含S里除v之外的顶点的、从a到v 具有最短可能长度的通路，后面接着从v到u的边。这种情形里它的长度
13、是 L (v) + w(v,u)。这样就证明了 (ii)为真，因为L (u) = minL L + w(v,u)。kk +1k (u), k (v)已经证明了定理1.定理1迪克斯特拉算法求出连通简单无向带权图里两个顶点之间最短通路的长度。现在可以估计迪克斯特拉算法的计算复杂性(就加法和比较而言)。这个算法使用 的迭代次数不超过n-1次，因为在每次迭代里添加一个顶点到特殊顶点集里。若可以估 计每次迭代所使用的运算次数，则大功告成。可以用不超过n-1次比较来找出不在Sk里 的带最小标记的顶点。于是我们使用一次加法和一次比较来更新不在S中的每一个顶点 k的标记，所以在每次迭代里的运算不超过2(n-1
14、)次，因为在每次迭代里要更新的标记不 超过n-1个。因为迭代次数不超过n-1次，每次迭代的运算次数不超过2(n-1)，所以 有下面的定理。定理2迪克斯特拉算法使用0(n2)次运算(加法和比较)来求出连通简单无向带 权图里两个顶点之间最短通路的长度。来源于：罗森(美).离散数学及其应用.北京：机械工业出版社，2003. 8(6)： 491-496.附:英文原文8.6 Shortest-Path Problems8.6.1 IntroductionMany problems can be modeled using graphs with weights assigned to their edg
15、es. 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 m
