文档介绍：利用Dijkstra算法计算最短路径
摘要
福格环游地球问题是一个十分典型的最短路径求解问题,题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长,并限定了福格的出行方向(福格选择的是往东走),给出起止地点后要求找出福格环游世界天数最短的最佳路径。
我们认为,这个问题的实质在于最短路径的求解和优化。我们对比图论中的多种最短路径算法,决定利用Dijkstra算法解决这个问题。
由于Dijkstra算法要求输入图G的关联矩阵,且图G为二维赋权图,而题中给出的地图可看成是三维环状地图,因此,我们对题设地图做相关处理,将其从起点处“切断”并展开为二维图,然后根据此图建立关联矩阵。同时,我们考虑到最短路径可能会与切断线有交点,在切断线以西找出若干地点一分为二,修改关联矩阵。
对于题目中缺失的两处数据,本文将以当时的交通数据为基础,经过合理的数据处理,结合Google Earth测距软件与题目数据的合理类比,补充缺失数据,完成关联矩阵。
得到关联矩阵后,我们分别以伦敦、纽约和上海作为起点,调整关联矩阵起点和终点,用matlab编程进行求解得到最短环游时间和最短路径,进而判断出所选择的路径是否能让他赢得赌注。根据我们的求解结果,在这三个城市,福格均能在80天内环游地球,赢得赌注。
本文进一步对此种算法的优缺点、灵敏度与推广性进行了分析,同时初步提出了两种优化方法。
关键词:最短路径算法 dijkstra算法算法优化
一、问题重述
儒勒•凡尔纳的著名小说《环游世界80天》中,英国绅士福格在伦敦与人打赌能够在80天内环游世界,这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船,然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图,福格选择的是往东走,每段路线所需要的天数显示在图上(见附录一),旅行的时间基于1872年能采用的旅行方式以及距离。
我们将解决以下问题:
1. 我们将设计一个算法为福格选择一条最佳路径,即环游世界天数最短,并判断所选择的路径是否能让他赢得赌注。
,如纽约或者上海,我们将分别设计最佳路径并判断所选择的路径是否能让他赢得赌注。
二、问题分析
福格环游地球问题是一个十分典型的最短路径求解问题,题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长,并限定了福格的出行方向(福格选择的是往东走),给出起止地点后要求找出福格环游世界天数最短的最佳路径。
本题实质在于最短路径的求解和优化,如何求解最短路径呢,我们联系到图论中求解最短路径的Dijkstra算法,然而,要满足Dijkstra算法的条件,首要任务是弄清如何处理题设所给的世界交通网络图。我们可以把题中给出的地图看成是三维环状地图,而Dijkstra算法要求输入图G的关联矩阵,且图G为二维赋权图,因此,我们应该对题设地图做相关处理,将其从起点处“切断”并展开为二维图,然后根据此图建立关联矩阵。但是,考虑到最短路径可能会与切断线有交点,我们必须在切断线以西找出若干地点一分为二,修改关联矩阵。
在创建关联矩阵的时候,必须考虑到如何估计两处缺失的数据,当时的地区交通状况文献已经无法查询,因此,我们只能根据当地周围相似地形地势处的已知交通状况进行估值。如何估值呢,我们用Google Earth对两地距离进行测量,并进行若干假设,与附近相似地形已知数据处进行同比例估值,得到近似结果。
对于题目提出的问题,分别以伦敦、纽约和上海作为起点,我们只需调整关联矩阵起点和终点用matlab编程进行求解即可得到最短环游时间和最短路径,从而判断出所选择的路径是否能让他赢得赌注。
三、基本假设
1、题目中给出的数据均准确。
2、题目中给出的数据均采用当时能达到的最高效的交通方式。
3、在环游地球的路程中,福格不会在任何地点因任何原因停留。
4、相似地理环境下,两地之间所需时间正比于两地距离。
5、Google Earth所测得的数据均准确。
6、相近地理环境下两地点间交通路线距离与直线距离近似成正比。
7、1870年至今数据缺失处地形地势未发生明显变动。
8、在旅行路途中因改变交通工具导致的可能的时间延误已计入数据所给时间。
9、在环球旅程中所有交通工具均能正常行驶。
四、符号说明
具体的符号使用将在具体使用处说明。
五、模型的建立与求解
缺失数据确定
题目所给数据中有两段路程具体数据缺失,需要自行估算。由于年代久远,当时的确切数据已很难查出,我们决定利用google earth软件对路径长度进行测距,结合当时的地理环境与题目已给出的数据进行估算。为了保证结果的合理性,对所有需要四舍五入的时间长度均采取进