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

利用Dijkstra算法计算最短路径摘要福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的出行方向（福格选择的是往东走），给出起止地点后要求找出福格环游世界天数最短的最佳路径。我们认为，这个问题的实质在于最短路径的求解和优化。我们对比图论中的多种最短路径算法，决定利用Dijkstra算法解决这个问题。由于Dijkstra算法要求输入图G的关联矩阵，且图G为二维赋权图，而题中给出的地图可看成是三维环状地图，因此，我们对题设地图做相关处理，将其从起点处“切断”并展开为二维图，然后根据此图建立关联矩阵。同时，我们考虑到最短路径可能会与切断线有交点，在切断线以西找出若干地点一分为二，修改关联矩阵。对于题目中缺失的两处数据，本文将以当时的交通数据为基础，经过合理的数据处理，结合GoogleEarth测距软件与题目数据的合理类比，补充缺失数据，完成关联矩阵。得到关联矩阵后，我们分别以伦敦、纽约和上海作为起点，调整关联矩阵起点和终点，用matlab编程进行求解得到最短环游时间和最短路径，进而判断出所选择的路径是否能让他赢得赌注。根据我们的求解结果，在这三个城市，福格均能在80天内环游地球，赢得赌注。本文进一步对此种算法的优缺点、灵敏度与推广性进行了分析，同时初步提出了两种优化方法。关键词：最短路径算法dijkstra算法算法优化一、问题重述儒勒•凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上（见附录一），旅行的时间基于1872年能采用的旅行方式以及距离。我们将解决以下问题：1．我们将设计一个算法为福格选择一条最佳路径，即环游世界天数最短，并判断所选择的路径是否能让他赢得赌注。2．若他在别的地方与人打赌，如纽约或者上海，我们将分别设计最佳路径并判断所选择的路径是否能让他赢得赌注。二、问题分析福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的出行方向（福格选择的是往东走），给出起止地点后要求找出福格环游世界天数最短的最佳路径。本题实质在于最短路径的求解和优化，如何求解最短路径呢，我们联系到图论中求解最短路径的Dijkstra算法，然而，要满足Dijkstra算法的条件，首要任务是弄清如何处理题设所给的世界交通网络图。我们可以把题中给出的地图看成是三维环状地图，而Dijkstra算法要求输入图G的关联矩阵，且图G为二维赋权图，因此，我们应该对题设地图做相关处理，将其从起点处“切断”并展开为二维图，然后根据此图建立关联矩阵。但是，考虑到最短路径可能会与切断线有交点，我们必须在切断线以西找出若干地点一分为二，修改关联矩阵。在创建关联矩阵的时候，必须考虑到如何估计两处缺失的数据，当时的地区交通状况文献已经无法查询，因此，我们只能根据当地周围相似地形地势处的已知交通状况进行估值。如何估值呢，我们用GoogleEarth对两地距离进行测量，并进行若干假设，与附近相似地形已知数据处进行同比例估值，得到近似结果。对于题目提出的问题，分别以伦敦、纽约和上海作为起点，我们只需调整关联矩阵起点和终点用matlab编程进行求解即可得到最短环游时间和最短路径，从而判断出所选择的路径是否能让他赢得赌注。三、基本假设1、1、23、4、相似地理环境下，两地之间所需时间正比于两地距离。5、GoogleEarth所测得的数据均准确。6、相近地理环境下两地点间交通路线距离与直线距离近似成正比。7、1870年至今数据缺失处地形地势未发生明显变动。8、在旅行路途中因改变交通工具导致的可能的时间延误已计入数据所给时间。9、在环球旅程中所有交通工具均能正常行驶。四、符号说明具体的符号使用将在具体使用处说明。五、模型的建立与求解5.1缺失数据确定题目所给数据中有两段路程具体数据缺失，需要自行估算。由于年代久远，当时的确切数据已很难查出，我们决定利用googleearth软件对路径长度进行测距，结合当时的地理环境与题目已给出的数据进行估算。为了保证结果的合理性，对所有需要四舍五入的时间长度均采取进位的方式，由此计算的总天数不会超过实际所需天数，得到的数据相对合理。15Minsk~19MoscowMinsk作为在19世纪飞速发展的工业城市与白俄罗斯首都，与Moscow之间有铁路连接，因此我们选取同以铁路连接的，Moscow与Berlin进行同类比对。由GoogleEarth测距，Berlin至Moscow距离1615.6公里，题目中数据为9天路程；Minsk至Moscow距离676公里。由此我们估算由Minsk至Moscow耗时4天。31Calcutta~32Bangkok我们认为由Calcutta至Bangkok的路途有两种方案，一是走陆路，利用马车大象的交通工具，由于两地之间有海湾相隔，只能绕行，大大增加了里程；二是走水路，由于Bangkok临近湄公河，Calcutta临近恒河，两城市均能方便而快捷的通过水路进入孟加拉湾，加上当时轮船是较为方便快捷的交通工具，因此水路能节省更多的时间。综上，我们选择第二种方案。有测距软件，两地距离1584公里。由Calcutta至Singapore同样走水路，有于需绕行大陆架，我们选择折线测距，距离3264公里，时长10天，由此可算得由Calcutta至Bangkok耗时4天。5.2利用dijkstra算法计算由伦敦出发的最短路径5.2.1算法选择此题是一道非常典型的最短路问题，解决最短路问题存在不同算法。在诸多最短路径算法中，Floyd算法和Warshall算法也可以解决这个问题，前者时间复杂性是0(B),而后者时间复杂性为0(2),二者时间复杂性均大于本模型所选用算法，因此，dijkstra算法的运算速度和运算量目前来说是最优的[1]。

数据初步处理由于dijkstra算法可计算两顶点间最短路，而题目中需要我们计算同地点出发同地点结束，因此我们需要对数据进行整理与合理简化。以伦敦为例详细表述。首先，我们将图以伦敦为界分为东西两个方向，设计一个新的节点1'作为旅途终点。同时我们发现，如果将与1相连的点都分别与1、1'相连，则可能会出现绕小圈的计算结果，达不到环游地球的目标路线。如果机械的将与1相连的点分为东西两部分分别与1,1'相连，则可能无法使计算所得的路程最短。因此，我们加设了两个点2'、3'。具体整理出的表格见下页。由此得到的数据表格将直接作为关联矩阵进行计算。在这种数据处理下，得到的结果将较为可靠。43rIJ1Lflcn收4,4,収収收4,4・収3333333333卜」fah.ihoh.jh.jhji—O中pa-ichcn4・3hjOM3ps-ich54・3hjmOU3ra-i43rIJ1Lflcn收4,4,収収收4,4・収3333333333卜」fah.ihoh.jh.jhji—O中pa-ichcn4・3hjOM3ps-ich54・3hjmOU3ra-idtui4-Ich-ichCJl43OOOOOOOOOOOOOOOCOOOOOoooooooooocooooooooooooooooooooooooooooooooooooooooooooooooooooO4OOOOOOO0OOOOOOOOOOOOOOO0OOOO0OOOOOOOOOOOOOOOQOOOOO****************0000***00*0*****ooooooooooooooaooooaaoooaaooooaooooaooooaaooooaooooooo400OOichoooooooooooooooooooooaoooooooooooooooaooooooooooooooooooooooooooooooooooooooooooooooo****************OOOOO0OOOO0*****OOOOOOOOOOQooo*****oooOOOOO0OOOOOOOOOOOOOOO0OOOO0OOOOOOOOOOO0004ooooooaooooaaoooaaooooaooooaooooaaooooaoohjtnoooooooooooooooooooooooooooooooooooooooo****************OOOOO0OOOO0*****OOOOOOOOOOQooo*****oooOOOOO0OOOOOOOOOOOOOOO0OOOO0OOOOOOOOOOO0004ooooooaooooaaoooaaooooaooooaooooaaooooaoohjtnooooooooooooooooooooooooooooooooooooooooooooaooooooooooooooooooooooooooooooooooooooooooooooooaoooooooooooooooooooooooaoooooooooooooooaoooooooooo****************OOOOO0OOOO0*****00000004000*****ooooooooOOOOO0OOOOOOOOOOOOOOO0OOOO0OOOOO000004****oooOOOOOooooLn****************0000***00*0*****OOOO3ch*****ooo*****aooooaaoooaaooooaooooaooooaaooooooooooooooooooaooooooooooooooooooOOOpaooooooooooooooooooooooooooooooOOOUJ****************OOOOO0OOOO0oooooooOOch4OOOOQ*********************oooooooooooooooaoooooooooooooooaoooooooooo****************OOOOO0OOOO0*****00000004000*****ooooooooOOOOO0OOOOOOOOOOOOOOO0OOOO0OOOOO000004****oooOOOOOooooLn****************0000***00*0*****OOOO3ch*****ooo*****aooooaaoooaaooooaooooaooooaaooooooooooooooooooaooooooooooooooooooOOOpaooooooooooooooooooooooooooooooOOOUJ****************OOOOO0OOOO0oooooooOOch4OOOOQ**************************0000***00*0*****oooooooo**********KjooOOiaooooaaoooaaooooaooooaoooooooaoaooooaaooohjaaoaKooohjoohjOOOOOOOOOOOOOOOOOOOOODJooooooooooooooooooooooooouikjoo!^oliooooooooooooooo**********************************hj00005OOOOO0OOOOOOOOOOOOOOOOOOGOOOOOOOOOO******************000*000**0***********0*00-1oooooooooooooooooooooooooooooooooooooo0040000cachooooaoooooooooooooooruoOOOUJoooooooooo0000000040300choooooooooooooooooooooOOOOO0OOOOOOOOOOOOOOOOOOOOQOOOOOOOOOO****************0*00*******ooooooooooo**********O*OOb.jaooooaaoooaaoooMcjiOOucji^OOOOaaooooaooooaooooaaoooooooooooooooooooooooooooooooooooooo****************ooooooo*****OOOOOOOOOOQ**********DJoooocnOOOOO0OOOOOOOOOOoooOOOOOOOOOOOOOOOQOOOOOOOOOOaooooaaoooaooooaooooaaooooaooooaooooaaoooooooooooooooooctikJOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOupoooooOOOOOooooooooooaooooooooooooooo**************************OOOOOOOOOOQ**********OOOOO0OOOOOOOOOOOOQOOOOOOOOOOOOOOOQOOOOOOOOOO****************ooooooooooo**********aooooaooooooooooooooooooooooooooooouikjoo!^oliooooooooooooooo**********************************hj00005OOOOO0OOOOOOOOOOOOOOOOOOGOOOOOOOOOO******************000*000**0***********0*00-1oooooooooooooooooooooooooooooooooooooo0040000cachooooaoooooooooooooooruoOOOUJoooooooooo0000000040300choooooooooooooooooooooOOOOO0OOOOOOOOOOOOOOOOOOOOQOOOOOOOOOO****************0*00*******ooooooooooo**********O*OOb.jaooooaaoooaaoooMcjiOOucji^OOOOaaooooaooooaooooaaoooooooooooooooooooooooooooooooooooooo****************ooooooo*****OOOOOOOOOOQ**********DJoooocnOOOOO0OOOOOOOOOOoooOOOOOOOOOOOOOOOQOOOOOOOOOOaooooaaoooaooooaooooaaooooaooooaooooaaoooooooooooooooooctikJOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOupoooooOOOOOooooooooooaooooooooooooooo**************************OOOOOOOOOOQ**********OOOOO0OOOOOOOOOOOOQOOOOOOOOOOOOOOOQOOOOOOOOOO****************ooooooooooo**********aooooaooooaaooooaooooaooooaaooooooooooaoooooooooooooooaooooooooooooooo4oOOOCJlooooooooooooooooooooooooooooooooooooooooooooooooodijkstra算法这个算法是通过为每个顶点V保留目前为止所找到的从s到V的最短路径来工作的。初始时，源点s的路径长度值被赋为0(d[s]=0)，同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点V除s外d[v]=°°)O当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展[2]。简而言之，这种算法就是逐点计算从起点到各个驻点的最短路程，进而得出两点之间的最短路径。算法计算过程中，将遍历所有点，因此所得的结果十分准确，与效率相关的分析将在后文给出。模型的求解我们利用matlab软件对模型进行了求解。得出的结果如下：环游世界共需79天，即可以赢得赌注

经历的的城市编号如下：1、6、7、12、17、22、23、28、31、32、35、37、39、41、47、50、53、1'。线路如下图所示：

以纽约和上海为起点的环球旅行以上海为起点数据处理与求解的过程与伦敦相仿，因此不再赘述，具体的数据处理等见附录。所得的结果如下：环球旅行共需75天。旅行所经城市路线图如下：23Athens24312』288Aden,44Marquesas45Panama"panamaSt.PetersburgStockholm^18.14Copenhagen/r2Beijing34Yokohama23Athens24312』288Aden,44Marquesas45Panama"panamaSt.PetersburgStockholm^18.14Copenhagen/r2Beijing34Yokohama‘、9436LosAngelesNovosibirsk^273/6\kpgu^>^./R^arcelona界&/^^S^Budapes?>raltar3AlgiersasablancaMaltaWinnipeg乡Denver^anFrancisy>^SanJuan43LosAngeles恥x2Singapore36^L3C4JakartaDarwinPorlMoresbyS；尹存畔SanDenver3^/^l/Newjoi^^MadridFrancisco3J52q/|\^oscow^-^.：19—2丄X浑盘沁哆，angko#^HongKong以纽约为起点数据处理也不再赘述，结果如下：环球旅行所需天数75天，路线图如下2318Beijing一Yokoham；362北4JakartaDarwinPortMoresby■^-^20[OSCOXV^^J23SanJuan,442318Beijing一Yokoham；362北4JakartaDarwinPortMoresby■^-^20[OSCOXV^^J23SanJuan,44MarquesasCairoNovosibirsk=7、45Panama436LosAngelesSan0Cnver'/NewYortFrancisco^i^552-、49(%aliimore^SLLouisSingapore^WinnipegSeat才48节豐^^Chicagc^2\WinnipegSea^e/^乡Denver✓^SanFr^cisg^l^〜SanJuan罗J24—^*43LosAngeles恥y・***2*45panamaKabul■24-^26ZXoel^^J>^hraivl?■^^calcuttaT^xKarachiHongKongMadrassXVSLPetersburgStockholm18^^^Copenhagen/144，疇沁K讥/汁呎叱次阳_7弋尸芒心6@爲^Madrid少建idape壮21弋IV六、模型优化Dijkstra算法是经典的解决最短路径问题的算法，它可以找出指定节点到其他各个节点间的最短路径，其主要思想是首先从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。这一点在上文中有详细的叙述。由其算法步骤可知，用标记法实现Dijkstra算法的主要步骤是从未标记的节点中选择一个权值最小的链路作为下一个转接点，而要选择一个权值最小的链路就必须把所有节点都扫描一遍，在大数量节点的情况下，这往往成为制约算法计算效率的关键因素。而本题正是这种情况。因此，我们认为，这一算法是可以进行优化处理的。6.1优化思路一通过分析传统Dijkstra算法的基本思路，我们认为，原始Dijkstra算法搜索的核心是从临时标记的点中选择一个权值最小的弧段，即每次在V—s查找距离源点最近的节点。这个过程可以近似为以源点为圆心的一系列同心圆，搜索过程没有考虑终点所在的方向和位置，在从源点出发的搜索过程中，其他节点与终点被搜索到的概率是相同的。为了减小算法中成功搜索的搜索的范围，以尽快达到目标节点，可以对原始Dijkstra算法进行优化。思路是：考虑到交通道路网络的搜索不同于一般数学上的网络搜索，节点位置总是与一定的空间位置相联系，所以从源点到终点的搜索也应具有一定的方向性。如果在运算过程中，首先沿着有效方向进行搜索，那么运算量将会大大降低［3］。根据分析，我们通过讨论，提出以下两种优化思路。一、引入一个辅助变量D,表示每个节点S•到终点的直线距离。对于每个当ii前所找到的终点Z.，确定下一个终点时Z.1时，如果D.1>D.，就将此路径舍弃，ii+1i+1i这样就减少了大量不必要的计算。为提高准确性，也可将D.2与D进行对比，或将Di+2与耳进行对比，依此类推，对比的两个点越“远”，准确性越高，当然，计算量也越大。考虑到距离与时间并不成严格的正比关系，而且实际问题复杂多变，由此计算的路径可能有偏差，因此，此种优化思路只适用于精度要求不高的最短路问题，不保证得出的路径是最短路径。二、引入一个辅助变量8.表示每个节点S.与终点连线到水平方向的夹角（逆i，i时针为正），对于每个当前所找到的终点Z.，确定下一个终点时，只佃.±90。的范围内搜索。ii同样，采用这种优化思路所得出的最短路也不一定是最短的路径，但计算的复杂度降低了很多。对于以上两种思路中的直线距离和角度如何得出，是需要进一步研究的问题。6.2优化思路二通过分析传统Dijkstra算法的运算过程，我们还发现，由于题目中给出的不同路线的交通网络图属于稀疏图，即图中很多地点之间是不能直接到达的，在传统Dijkstra算法中它们之间路径的权重为因此，在运算的过程中，要进行很多次与*的比较，这些比较是完全没有必要的。通过查找资料，我们发现可以用邻接多重表的存储结构解决这一问题。6.2.1邻接多重表结构临界多重表是无向图的一种链式存储结构，类似于链表结构。其中包括顶点结构，和边的结构。顶点的结构由两个域组成：第一个域中存储标示该顶点的信息，本题中即为各地点的标号；另一个域中存储一个指针，指向第一条与该顶点相连的边。datafirstedge边的结构由五个域组成，如下图。其中，i和j存储这条边的两个顶点在图中的编号，ilink和jlink都是指针域，其中ilink指向下一条与顶点i连接的边，jlink指向下一条与顶点j连接的边。weight域为指向和该边相关的各种信息的指针域，如，路径的权值，在本题中为每段路线所需要的天数。infoivexilinkjvexjlink在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。采用邻接多重表来表示无向图，节点中设计一个域用来存放任意两点之间的权值。节点用来表示边，若边不存在的话，则不新建节点［4］。6.2.2邻接多重表优化模型分析传统Dijkstra算法的时间复杂度构造邻接矩阵的时间复杂度分析假设无向图的顶点数为n，无向图的边数e(OWeWn(ltl—1)/2)。如果用邻接矩阵A来表示，则要占用NXN的空间。对于稀疏图(evvn(n-1)/2)，在矩阵中存储很多零元素，对存储空间造成了浪费；此外，要建立一个邻接矩阵，需要给矩阵的每一个元素初始化，约要n2次，，对其中有邻接顶点的元素赋值约要e次，每次赋值前对顶点查编号需要0(n)。时间复杂度为0(n2+eXn)。6・2・2・1・2基于邻接矩阵的Dijikstra算法程序的时间复杂度分析根据算法程序分析该算法的运行时间，外层循环的时间复杂度是0(n—1)，嵌套的内层循环执行的时间是0(n)，因此得到，采用邻接矩阵作为存储结构的Dijkstra算法程序的总时间复杂度是0(n2)。6・2・2・2基于邻接多重表的Dijkstra算法时间复杂度6・2・2・2・1构造邻接多重表的时间复杂度分析构造邻接多重表分为两个步骤，首先是寻找到依附于某一顶点的最后一条边的指针；其次是在图的邻接多重表中插入一条边。寻找依附于某一顶点的最后一条边的指针的算法程序如附录6所示。由图论可知，对于n阶完全图而言，与顶点V关联的边的条数为n—1,即依附于顶点V的链表的最长的长度为n—1。因此，循环最多执行n—1。通过上述分析得到，第一步的时间复杂度为0(n—1)。插入边的程序如附录7所示。该算法是按照顶点递增顺序插入边。若插入e条边，则调用e次InsertEdge()函数，它所耗费的时间为0(e)。此外，插入N个顶点的时间复杂度是0(n)。因此，采用邻接多重表，构造一个具有n个顶点和e条边的无向图的时间复杂度是0(n+eX(n—1))。6.2.2.2.2基于邻接多重表的Dijikstra算法程序的时间复杂度分析基于邻接多重表的Dijkstra算法程序如附录8所示，算法中，针对边的操作，是按照依附于顶点的边的递增顺序搜索边。已知s为已求得最短路径的终点的集合，V为未求得最短路径的终点的集合，假设从vi到vj有边(vi,vj)(ivj),vieS且vjeV，可证明：边(vi,vj)仅被访问一次。由此得到，执行完第一个循环总的时间复杂度是0(e)。所以，基于邻接多重表的Dijkstm算法程序的时间复杂度是0(e)。

基于以上分析，采用邻接多重表结构确实可以使计算简化。邻接多重表优化算法的适用范围通过6.2.2的分析，只有当e<<n（n-1）/2时，时间复杂度才可以降低，因此，使用邻接多重表存储结构进行优化的思路只是用于稀疏图。而本题恰好符合。七、灵敏度分析七、灵敏度分析本算法具有很好的灵敏度，即若路径权值或起点位置发生改变且足以改变理论最短路径，本算法可灵敏地作出相应改变，找出最短路径；若改变不足以改变理论最短路径，本算法找出的最短路径则不会有明显变动。八、模型评价与推广8.1模型的优点本模型将福格环游地球具有54个地点的三维线路图（地球表面）根据具体情况抽象成了具有55个或更多顶点的二维赋权图G（将起点一分为二三维环状图断成二维平面图），并将没有连通的两点权值设为0在matlab程序中将其转变成无穷大，方便运用本模型建立的算法对其进行路径分析。根据图论知识，凡是时间复杂性为戸％三的算法（其中匚；八为一二元多项式），著名数学家J.Edmonds称之为“好算法"（Goodalgorithm）或多项式时间算法，区别于运算量大的指数型时间算法（时间复杂性无法用输入长n的多项式作为其上界的算法），用以评估算法的运算效率，而实践证明，好算法与指数型时间算法的运算效率有天壤之别。在本模型中，复杂性计算如下：加法：比较：加法：比较：v^S：（丫-丄）（其中i为G的顶点数）总共算得其时间复杂性为0（讶），是多项式时间算法，即好算法。此外，我们找到了其它两种算法求最短路径，分别是Floyd算法和Warshall算法。经计算，前者时间复杂性是O（讨），而后者时间复杂性为O（讨），二者时间复杂性均大于本模型所选用算法，因此，这种算法的运算速度和运算量目前来说是最优的。8.2模型的缺点由于此题所给地图是闭合的，要求求出从A出发然后绕地球一圈回到A的最短路径，而我们选用的算法只能求出从A到B（A与B为不同地点）的最短路径，因此，在制作关联矩阵时，我们只能将地图从A点截断（即将A分为A和A'抽象成二维的赋权图G,这里就产生了较为复杂的数据处理问题，因为我们在制作关联矩阵的过程中，需要考虑哪些路应该“截断”（权值设为0），不同的起点需要考虑不同的情况，有不同的关联矩阵，给模型的求解过程带来不便。另外，用matlab计算出的最短路径编号并不一定和地点编号一一对应，要找出实际路径必须以最短路径编号作为索引在关联矩阵中找到对应地点编号，因为此算法要求起点终点必须在关联矩阵的第一行第一列和最后一行最后一列，并按照关联矩阵的元素位置序号输出路径。但是此缺点带来的工作量可以忽略不计[5]。8.3模型的推广本算法不仅适用于本题环游地球的最短路径求解问题，只要将任何实际问题抽象为赋权图G，并有确定的起点与终点，即可由本算法求出最短路径，最短的时间，最短的路程等等。实际生活中的许多问题都可归结于图论中的最短路径问题，如：电子导航、交通旅游、公交出行，管道铺设，厂区布局以及电力、通讯中的很多问题等。这里的最短路径不仅仅指地理意义上的距离最短，可引申为最少费用、最短时间、延时最短、吞吐量最大等约束条件。而此模型正是基于典型最短路问题建立的，因此，本文所提供的方法同样适用于解决这些这些问题。对于一些多阶段决策问题，由于它的特殊性，可将过程分成若干个互相联系的阶段，在其每一阶段都需要作出决策，从而使整个过程达到最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状况，有影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，确定了整个决策过程的活动路线。利用通常的动态规划模型求解是比较困难的，比如，要写出其动态规划的递推关系难度很大，并且不易用程序语言表述，对于此类问题，我们可以将实际问题数学抽象成相应的树图，根据实际情况给图的每一边赋上相应的权值，将它转化为最短路径问题，并利用上述模型求解，这样的转换可简化复杂的动态规划实际问题，并方便地用程序语言进行表达。此外，基于最短路径问题，我们还可以将本文提出的算法做适当修改，求出最短路径、次短路径等等，这对一些实际问题如交通规划的不同方案选取、旅游路线方案的选取等有重要意义。九、参考文献陈东彦等，数学建模，科学出版社卜月华，图论及其应用，东南大学出版社章永龙，Dijkstra，最短路径算法优化，南昌工程学院学报，Vol.25，No.3宋金华，Dijkstra算法程序的优化，海南广播电视大学学，2008，No.4殷剑宏，图论及其算法，中国科学技术大学出版社附录一：题目数据图附录-ibirsk附录二：纽约数据整理附录四：上海数据整理_[3333333卜」卜」卜」卜」143卜」屮do--iOOOooooooooooooooooooooooooOOOooooooooooooooooooooooooOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOCcaOUJOOOOOOOOdiOOitiOOOooo4000oooooooooooooooooooooooooooooooooooooooooooooo4000ooooooooooooooooooooooooooooooooooooooooooo000000000000000000000000000000000000000Ln0000»^000ch000000SOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOMLnOOOOtJOOOOcaOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOuicajOOmOOO^OoaooooaooooooooooooooooooooooooowMwo»^o--m3Ooooo--ioooooaoooh.joaooooaoooooooooooooooooooooo^ooMoowoooocoooocjioooooaooowOQOOOOQOOOOQOOOOQOOOOQOOOOQOOOhJ3OOOru!&OOOOQOOOOQOOOOQOOO4OOOOOOOOOOOOOOOOOOOOOOOOOLnOOOEJOOOOMwOOOOOOOOOOOOOOOOOOOtJi000000000000000000000000004400400300lOOOOOOOOOOOOOOOOOOrh0000000000000000000000000300000402000000000000000000000-1OOOOOOOOOOOOOOOOOOOOOOOOMOOOOOOOwOi^OOOOOOOOOOOOOOOOOOOOcaOOOOOOOOOOOOOOOOOOOOOOOMOOOKJOOOOOOOOEJOOOOOOOOOOOOOOOOOOU3OOOOOOOOOOOOOOOOOOOOwOOOOOOOOOwOuiOOOOOOOOOOOOOOOOOOOOOOh.1oaooooaoooooooooooooojooooooooiuoaoooooooocooooooooooaooowOOOOOOOOOOOOOOOOwchOOOOOOOOhJOOOOOOOOOOOOOOOOOOOOOOOOOOOOmoaoaaoaaouiooDaaotJoaaoooaaoooaaoooaaoooaaoooaaoooaaoooaaoLjkaool^bkjoooooooooooooooooooooooooooooooooooooOOOOOCi^chOOOOU^OLnOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOmOQOO4Q3OQ£hOQOOOOQOOOOQOOOOQOOOOQOOOOQOOOOQOOOOQOOOOQOOQ営岂0005403440000000000000000000000000000000000000000000000040304000000000000000000000000000000000000000000000000器3ni

附录五：matlab程序function[d,path]=dijkstra(W,s,t)[n,m]=size(W);ix=(W==0);W(ix)=inf;ifn~=m,error('SquareWrequired');endvisited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;fori=l:(n-l),%每个节点与起点的关系ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);[a,u]=min(vec);visited(u)=l;forv=l:n,if(W(u,v)+dist(u)<dist(v)),dist(v)=dist(u)+W(u,v);parent(v)=u;end;end;endifparent(t)〜=O,path=t;d=dist(t);%最短路径whilet~=s,p=parent(t);path=[ppath];t=p;end;end;将处理的的数据保存为M文件调用的时候W=xlsread('R:\beijing.xlsx');s=l;t=57;[d,path]=Dijkstra(W,s,t)附录六模型优化的C语言程序1EdgePtrLastEdge(GraphType*