最短路径文献翻译终极版.docVIP

单位代码 01 学　　号 090111006 分 类 号 O24 密 级 文献翻译 最短通路问题 院(系)名称 信息工程学院 专业名称 信息与计算科学 学生姓名 许秀成 指导教师 孙贵玲 2013年 3 月 10 日 8. 6 最短通路问题 许多问题可以用边上赋权的图来建模。考虑一下航线系统如何建模。如果用顶点表示城市，用边表示航线。给边赋上城市之间的距离，就可以为涉及距离的问题建模；给边赋上飞行时间，就可以为涉及飞行时间的问题建模；给边赋上票价，就可以为涉及票价的问题建模。图8—61显示了给一个图的边赋权的三种不同方式，分别表示距离，飞行时间和票价。 图 8-61 为航线系统建模的带权图 给每条边赋上一个数的图称为带权图。带权图用来为计算机网络建模。通信成本（比如租用电话线的月租费）、计算机在这些线路上的响应时间或是计算机之间的距离等都可以用带权图来研究。图8—62显示一些带权图，它们表示给计算机的图的边赋权的三种方式，分别对应成本、响应时间和距离。 与带权图有关的几种类型的问题出现得很多。确定网络里两个顶点之间长度最短的通路就是一个这样的问题。说的更具体些，设带权图里一条通路的长度是这条通路上各边的权的总和。（读者应当注意，对术语长度的这种用法，与表示不带权的图的通路里边数的长度的用法，这两者是不同的。）问题是：什么是最短通路，即什么是在两个给定顶点之间长度最短的通路?例如，在图8—61所示带权图表示的航线系统里，在波士顿与洛杉矶之间以空中距离计算的最短通路是什么？在波士顿与洛杉矶之间什么样的航班组合的总飞行时间（即在空中的总时间，不包括航班之间的时间）最短？在这两个城市之间的最低费用是多少？ 图 8-62 为计算机网络建模的带权图 在图8—62所示的计算机网络里，连接旧金山的计算机与纽约的计算机所需要的最便宜的一组电话线是什么？哪一组电话线给出旧金山与纽约之间的通信的最短响应时间？哪一组电话线有最短的总距离？与带权图有关的另外的一个重要问题是：求访问完全图每个顶点恰好一次的、总长度最短的回路。这就是著名的旅行商问题，它求一位推销商应当以什么样的顺序来访问其路程上的每个城市恰好一次，使得他旅行的总距离最短。本节后面将讨论旅行商问题。 最短通路算法 求带权图里两个顶点之间的最短通路有几个不同的算法。下面将给出荷兰数学家E·迪克斯特拉在1959年所发现的一个解决无向带权图中最短通路问题的算法，其中所有的权都是正数。可以很容易地将它修改后来解决有向图里的最短通路问题。 在给出这个算法的形式化表示之前将给出一个启发性的例子。 例 1 在图8—63所示的带权图里，和之间的最短通路的长度是多少？ 图 8—63 解 虽然通过观察就容易求出最短通路，但是需要想出一些有助于理解迪克施特拉算法的办法。要解决的问题就是：求从到各个相继的顶点的最短通路，直到到达为止。 从开始、（直到到达终点为止）不包括除以外的顶点的唯一通路是,和,。因为,和，的长度分别是4和2，所以是与最近的顶点。 可以通过查看（直到到达终点为止）只经过和的所有通路，来求出下一个最靠近的顶点。到的最短通路仍然是，，长度为4，而到的最短通路是,，长度为5。所以，下一个与最靠近的顶点是。 为了找出第三个与最近的顶点，只需要检查（直到到达终点为止）只经过了和的那些通路。存在长度为7到的通路，即,以及长度为6到的通路，即。所以，是下一个与最靠近的顶点，而且到的最短通路的长度为6。 例 1 说明了在迪克斯特拉算法里使用的一般原理。注意通过检查就可能求出从到最短通路。不过，无论对人还是对计算机来说，检查边数很多的图都是不切实际的。 现在将考虑一般问题：在无向联通简单带权图里，求出与之间的最短通路的长度。迪克斯特拉算法如下进行：求出从到第一个顶点的最短通路的长度，从到第二个顶点最短通路的长度，以此类推，直到求出到的最短通路长度为止。 这个算法依赖于一系列的迭代。通过在每次跌代里添加一个顶点来构造出特殊顶点的集合。在每次跌代里完成一个标记过程。在这个标记过程，只包括特殊顶点的从到的最短通路的长度来标记。添加到特殊顶点集里的顶点是尚在集合之外的那些顶点中带有最小标记的顶点。 现在给出迪克斯特拉算法的细节。它首先用0标记而用∞标记其余的顶点。用记号和表示在没有发生任何迭代之前的这些标记（下标0表示“第0次”迭代)。这些标记是从到这些顶点的最短通路的长度，其中这些通路只包含顶点。（因为不存