迪杰斯特拉算法计算最短路径

《迪杰斯特拉算法计算最短路径》由会员分享，可在线阅读，更多相关《迪杰斯特拉算法计算最短路径（17页珍藏版）》请在金锄头文库上搜索。

1、利用利用 DijkstraDijkstra 算法计算最短路径算法计算最短路径摘摘 要要福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时 世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的 出行方向（福格选择的是往东走） ，给出起止地点后要求找出福格环游世界天数 最短的最佳路径。 我们认为，这个问题的实质在于最短路径的求解和优化。我们对比图论中 的多种最短路径算法，决定利用 Dijkstra 算法解决这个问题。 由于 Dijkstra 算法要求输入图 G 的关联矩阵，且图 G 为二维赋权图，而题 中给出的地图可看成是三维环状地图，因此，我们对题设地图做相关处理，

2、将 其从起点处“切断”并展开为二维图，然后根据此图建立关联矩阵。同时，我 们考虑到最短路径可能会与切断线有交点，在切断线以西找出若干地点一分为 二，修改关联矩阵。 对于题目中缺失的两处数据，本文将以当时的交通数据为基础，经过合理 的数据处理，结合 Google Earth 测距软件与题目数据的合理类比，补充缺失数 据，完成关联矩阵。 得到关联矩阵后，我们分别以伦敦、纽约和上海作为起点，调整关联矩阵起 点和终点，用 matlab 编程进行求解得到最短环游时间和最短路径，进而判断出 所选择的路径是否能让他赢得赌注。根据我们的求解结果，在这三个城市，福 格均能在 80 天内环游地球，赢得赌注。 本文

3、进一步对此种算法的优缺点、灵敏度与推广性进行了分析，同时初步提 出了两种优化方法。关键词：关键词：最短路径算法 dijkstra 算法 算法优化一、问题重述一、问题重述儒勒凡尔纳的著名小说环游世界 80 天中，英国绅士福格在伦敦与人 打赌能够在 80 天内环游世界，这在当时的 1872 年是一个了不起的壮举。当时 最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴 子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格 选择的是往东走，每段路线所需要的天数显示在图上（见附录一） ，旅行的时间 基于 1872 年能采用的旅行方式以及距离。 我们将解决以下问题： 1

4、 我们将设计一个算法为福格选择一条最佳路径，即环游世界天数最短，并 判断所选择的路径是否能让他赢得赌注。 2若他在别的地方与人打赌，如纽约或者上海，我们将分别设计最佳路径并判 断所选择的路径是否能让他赢得赌注。二、问题分析二、问题分析福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时 世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的 出行方向（福格选择的是往东走） ，给出起止地点后要求找出福格环游世界天数 最短的最佳路径。 本题实质在于最短路径的求解和优化，如何求解最短路径呢，我们联系到 图论中求解最短路径的 Dijkstra 算法，然而，要满足 Dijkst

5、ra 算法的条件， 首要任务是弄清如何处理题设所给的世界交通网络图。我们可以把题中给出的 地图看成是三维环状地图，而 Dijkstra 算法要求输入图 G 的关联矩阵，且图 G 为二维赋权图，因此，我们应该对题设地图做相关处理，将其从起点处“切断” 并展开为二维图，然后根据此图建立关联矩阵。但是，考虑到最短路径可能会 与切断线有交点，我们必须在切断线以西找出若干地点一分为二，修改关联矩 阵。 在创建关联矩阵的时候，必须考虑到如何估计两处缺失的数据，当时的地 区交通状况文献已经无法查询，因此，我们只能根据当地周围相似地形地势处 的已知交通状况进行估值。如何估值呢，我们用 Google Earth

6、 对两地距离进行 测量，并进行若干假设，与附近相似地形已知数据处进行同比例估值，得到近 似结果。 对于题目提出的问题，分别以伦敦、纽约和上海作为起点，我们只需调整关联 矩阵起点和终点用 matlab 编程进行求解即可得到最短环游时间和最短路径，从 而判断出所选择的路径是否能让他赢得赌注。三、基本假设三、基本假设1、题目中给出的数据均准确。2、题目中给出的数据均采用当时能达到的最高效的交通方式。 3、在环游地球的路程中，福格不会在任何地点因任何原因停留。 4、相似地理环境下，两地之间所需时间正比于两地距离。 5、Google Earth 所测得的数据均准确。 6、相近地理环境下两地点间交通路线距

7、离与直线距离近似成正比。 7、1870 年至今数据缺失处地形地势未发生明显变动。 8、在旅行路途中因改变交通工具导致的可能的时间延误已计入数据所给时间。 9、在环球旅程中所有交通工具均能正常行驶。四、符号说明四、符号说明具体的符号使用将在具体使用处说明。五、模型的建立与求解五、模型的建立与求解5.1 缺失数据确定缺失数据确定题目所给数据中有两段路程具体数据缺失，需要自行估算。由于年代久远， 当时的确切数据已很难查出，我们决定利用 google earth 软件对路径长度进行测 距，结合当时的地理环境与题目已给出的数据进行估算。为了保证结果的合理 性，对所有需要四舍五入的时间长度均采取进位的方式

8、，由此计算的总天数不 会超过实际所需天数，得到的数据相对合理。 5.1.1 15Minsk19MoscowMinsk 作为在 19 世纪飞速发展的工业城市与白俄罗斯首都，与 Moscow 之间有铁路连接，因此我们选取同以铁路连接的，Moscow 与 Berlin 进行同类 比对。由 Google Earth 测距，Berlin 至 Moscow 距离 1615.6 公里，题目中数据 为 9 天路程；Minsk 至 Moscow 距离 676 公里。由此我们估算由 Minsk 至 Moscow 耗时 4 天。 5.1.2 31Calcutta32Bangkok 我们认为由 Calcutta 至

9、Bangkok 的路途有两种方案，一是走陆路，利用马 车大象的交通工具，由于两地之间有海湾相隔，只能绕行，大大增加了里程； 二是走水路，由于 Bangkok 临近湄公河，Calcutta 临近恒河，两城市均能方便 而快捷的通过水路进入孟加拉湾，加上当时轮船是较为方便快捷的交通工具， 因此水路能节省更多的时间。综上，我们选择第二种方案。有测距软件，两地 距离 1584 公里。由 Calcutta 至 Singapore 同样走水路，有于需绕行大陆架，我 们选择折线测距，距离 3264 公里，时长 10 天，由此可算得由 Calcutta 至 Bangkok 耗时 4 天。 5.2 利用利用 di

10、jkstra 算法计算由伦敦出发的最短路径算法计算由伦敦出发的最短路径 5.2.1 算法选择算法选择 此题是一道非常典型的最短路问题，解决最短路问题存在不同算法。 在诸多最短路径算法中， Floyd 算法和 Warshall 算法也可以解决这个问题， 前者时间复杂性是 O（） ，而后者时间复杂性为 O（） ，二者时间复杂性43均大于本模型所选用算法，因此，dijkstra 算法的运算速度和运算量目前来说是 最优的1。 5.2.1 数据初步处理数据初步处理 由于 dijkstra 算法可计算两顶点间最短路，而题目中需要我们计算同地点出 发同地点结束，因此我们需要对数据进行整理与合理简化。以伦敦为

11、例详细表 述。 首先，我们将图以伦敦为界分为东西两个方向，设计一个新的节点 1作为 旅途终点。同时我们发现，如果将与 1 相连的点都分别与 1、1相连，则可能 会出现绕小圈的计算结果，达不到环游地球的目标路线。如果机械的将与 1 相 连的点分为东西两部分分别与 1,1相连，则可能无法使计算所得的路程最短。 因此，我们加设了两个点 2 、3 。具体整理出的表格见下页。 由此得到的数据表格将直接作为关联矩阵进行计算。 在这种数据处理下，得到的结果将较为可靠。5.2.2 dijkstra 算法算法这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径 来工作的。初始时，源点 s

12、 的路径长度值被赋为 0（ds=0） ， 同时把所有其他 顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对 于 V 中所有顶点 v 除 s 外 dv= ） 。当算法结束时，dv中储存的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijstra 算法的基础操作是 边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 u 的最短路径可以通过将 边(u,v)添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 du+w(u,v)。 如果这个值比目前已知的 dv的值要小，我们可以用新值来替代当前 dv中的值。拓展边的操作一直执行到所有的 dv都代

13、表从 s 到 v 最短路径的花费。这 个算法经过组织因而当 du达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 dv的值已经 是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合 S 初始状态为空， 而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 du值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边(u,v)进 行拓展2。简而言之，这种算法就是逐点计算从起点到各个驻点的最短路程，进而得 出两点之间的最短路径。算法计算过程中，将遍历所有点，因此所得的结果十 分准确，与效率

14、相关的分析将在后文给出。 5.2.3 模型的求解模型的求解 我们利用 matlab 软件对模型进行了求解。 得出的结果如下： 环游世界共需 79 天，即可以赢得赌注 经历的的城市编号如下： 1、6、7、12、17、22、23、28、31、32、35、37、39、41、47、50、53、1 。 线路如下图所示：5.3 以纽约和上海为起点的环球旅行以纽约和上海为起点的环球旅行 5.3.1 以上海为起点以上海为起点数据处理与求解的过程与伦敦相仿，因此不再赘述，具体的数据处理等见 附录。所得的结果如下： 环球旅行共需 75 天。 旅行所经城市路线图如下：5.3.2 以纽约为起点以纽约为起点 数据处理也

15、不再赘述，结果如下： 环球旅行所需天数 75 天，路线图如下：六、模型优化六、模型优化Dijkstra 算法是经典的解决最短路径问题的算法，它可以找出指定节点到其他各个节点间的最短路径，其主要思想是首先从源点求出长度最短的一条路 径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。这一 点在上文中有详细的叙述。 由其算法步骤可知，用标记法实现Dijkstra 算法的主要步骤是从未标记的 节点中选择一个权值最小的链路作为下一个转接点，而要选择一个权值最小的 链路就必须把所有节点都扫描一遍，在大数量节点的情况下，这往往成为制约 算法计算效率的关键因素。而本题正是这种情况。因此，我们认为

16、，这一算法 是可以进行优化处理的。 6.1 优化思路一优化思路一 通过分析传统Dijkstra 算法的基本思路，我们认为，原始Dijkstra算法搜索 的核心是从临时标记的点中选择一个权值最小的弧段，即每次在Vs查找距离 源点最近的节点。这个过程可以近似为以源点为圆心的一系列同心圆，搜索过 程没有考虑终点所在的方向和位置，在从源点出发的搜索过程中，其他节点与 终点被搜索到的概率是相同的。为了减小算法中成功搜索的搜索的范围，以尽 快达到目标节点，可以对原始Dijkstra算法进行优化。思路是：考虑到交通道路 网络的搜索不同于一般数学上的网络搜索，节点位置总是与一定的空间位置相 联系，所以从源点到终点的搜索也应具有一定的方向性。如果在运算过程中， 首先沿着有效方向进行搜索，那么运算量将会大大降低3。 根据分析，我们通过讨论，提出以下两种优化思路。 一、引入一个辅助变量Di，表示每个节点Si到终点的直线距离。对于每个 当前所找到的终点Zi，确定下一个终点时Zi+1时，如果Di+1Di，就将此