双向dijkstra算法及中间链表加速

《双向dijkstra算法及中间链表加速》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据第21卷第951计算机仿真2004年9月===================================================================：==============================；=====一文章编号：1006—9348(2004)09—0078—04双向Dijkstra算法及中间链表加速方法靳晓强(华中科技大学水利水电及数字化工程学院，湖北武汉430074)摘要：该文提出了双向Dijkstra算法及中间链表加速方法。应用双向Oijkstra算法经中间链表加速后在近5000个顶点的华盛顿地图上寻找两个

2、指定顶点之间的最短路径，在主频633MHz的计算机上最长用时不超过31．1毫秒。双向Dijkstra算法的效率比传统Dijkstra算法平均提高40％以上，而且图的顶点越多，效果越盟显。关键词：最短路径；算法；链表中圈分类号：7I鹳12文献标识码：BBi—directionalDijkstraAlgorithmandtheAccelerationofIntermediateListJINXiao——qiang(DepartmentofHydropowerandAutomationEng．，I-lUST，WuhanHubei430074，China)ABSTRACT：

3、ThisarticleisintendedtOproposeabi—directionalalgorithmandtheaccelerationofintermediatelist．Whenidentifyingtheshortcutbetween2designatedvertexesOilamapofWashingtonwithnearly5．000vertexesbywayofbi～di—rectiorl&l蹦k咖algorithmandaccelerationofintermediatelistonacomputerwithaprimaryfrequencyo

4、f633MHz，themaximumtimeneededislessthan31．1MSEL．Theefficiencyofbi—directionalDijkstra蛳蜘isgenerallymorethan40％higberthanthatofthetraditionalt)ijks￡ra蚴蛔．Thenlol'evenexesthereareOilthemap，thehighertheefficiencywillbe．KEYWORI)S：Shortcut；Algorithm；List1引言最短路径算法在电子导航、运输科学、交通旅游以及电力、通讯等领域有着广泛的应

5、用，已成为GIS网络分析的主要功能之一。最短路径不仅指地理意义上的距离最短，还可以引申到最少时间、最低费用等。由于最短路径问题在实际中常用于各种应急系统等(如110报警、119火警、120急救等系统)，这些系统都要求快速计算出到出事地点的最佳路线，即使普通用户也不能容忍长时间等待，因而此类系统对计算时间要求很高。目前国内外一致公认较好的算法有Dijkstra算法和Floyd算法，但它们的时间复杂度与图的顶点数的平方成正比，在顶点较多的情况下就难以满足实际运算的需要。本文提出的双向Dijkstra算法是对Dijkstra算法的一种改进，经实验证明，在顶点数较多的图上是

6、一种很优秀的最短路径算法。收稿日期：2003—03—28—78—2．1t歧ikstra算法的基本思想首先从起点求出长度最短的一条路径，然后参照它求出长度次短的一条最短路径，依次类推，直到到达终点为止。2．2Dijkstra算法基本方法假设每个顶点都有一对标号(di，pi)，其中也是从起点s到顶点i的最短路径的长度(从顶点到其本身的最短路径长度设为零)；pl则是从s到j的最短路径中j点的前一顶点。求解从起点s到顶点i的最短路径算法的基本过程如下：1)初始化。起点设置为：①dB=0，p8为空；②所有其他顶点：di=∞，pi=?；③标记起点s，其他所有顶点设为未标记的。2

7、)检验从所有已标记了的顶点k到其邻接点J的距离，并设置：dj=minedj，dk+lkj]式中，l“是从顶点k到顶点J的直接连接距离。3)从所有未标记的顶点中，选取di中最小的一个顶点i，i就被选为最短路径中的一个顶点，标记顶点i。4)找到顶点i的前一顶点。从已标记的顶点中找相应的万方数据顶点j。，作为前一顶点，设置：Pi=J’5)如果顶点i是终点，则计算结束，否则，转到2)继续。3用中间链表加速Dijks昀算法3．1中间链表加速D柚l【sh翟算法的基本思想在蹦kstra算法基本方法中，把所有没有标记但同已标记顶点邻接的顶点存入一个链表，在第三步中每对一顶点做标