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

临界多重表是无向图的一种链式存储结构，类似于链表结构。其中包括顶点结构，和边的结构。

顶点的结构由两个域组成：第一个域中存储标示该顶点的信息，本题中即为各地点的标号；另一个域中存储一个指针，指向第一条与该顶点相连的边。

data firstedge 边的结构由五个域组成，如下图。其中，i和j存储这条边的两个顶点在图中的编号，ilink和jlink都是指针域，其中ilink指向下一条与顶点i连接的边，jlink指向下一条与顶点j连接的边。weight域为指向和该边相关的各种信息的指针域，如，路径的权值，在本题中为每段路线所需要的天数。 info ivex ilink jvex jlink 在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。采用邻接多重表来表示无向图，节点中设计一个域用来存放任意两点之间的权值。节点用来表示边，若边不存在的话，则不新建节点[4]。 6.2.2邻接多重表优化模型分析

6.2.2.1传统Dijkstra 算法的时间复杂度 6.2.2.1.1构造邻接矩阵的时间复杂度分析

假设无向图的顶点数为n，无向图的边数e(0≤e≤n(1tl一1)／2)。如果用邻接矩阵A来表示，则要占用N×N的空间。对于稀疏图（e<

根据算法程序分析该算法的运行时间，外层循环的时间复杂度是O(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。通过上述分析得到，第一步的时间复杂度为O(n一1)。插入边的程序如附录7所示。该算法是按照顶点递增顺序插入边。若插入e条边，则调用e次InsertEdge()函数，它所耗费的时间为0(e)。此外，插入N个顶点的时间复杂度是0(n)。因此，采用邻接多重表，构造一个具有n个顶点和e条边的无向图的时间复杂度是0(n+e×(n—1))。

6.2.2.2.2基于邻接多重表的Dijikstra算法程序的时间复杂度分析

基于邻接多重表的Dijkstra算法程序如附录8所示，算法中，针对边的操作，是按照依附于顶点的边的递增顺序搜索边。已知s为已求得最短路径的终点的集合，V为未求得最短路径的终点的集合，假设从vi到vj有边(vi，vj)(i

基于以上分析，采用邻接多重表结构确实可以使计算简化。 6.2.3 邻接多重表优化算法的适用范围

通过6.2.2的分析，只有当e<

七、灵敏度分析

本算法具有很好的灵敏度，即若路径权值或起点位置发生改变且足以改变理论最短路径，本算法可灵敏地作出相应改变，找出最短路径；若改变不足以改变理论最短路径，本算法找出的最短路径则不会有明显变动。

八、模型评价与推广

8.1 模型的优点

本模型将福格环游地球具有54个地点的三维线路图（地球表面）根据具体情况抽象成了具有55个或更多顶点的二维赋权图G（将起点一分为二三维环状图断成二维平面图），并将没有连通的两点权值设为0，在matlab程序中将其转变成无穷大，方便运用本模型建立的算法对其进行路径分析。

根据图论知识，凡是时间复杂性为

的算法（其中

为一二元多项

式），著名数学家J.Edmonds 称之为“好算法”（Good algorithm）或多项式时间算法，区别于运算量大的指数型时间算法（时间复杂性无法用输入长n的多项式作为其上界的算法），用以评估算法的运算效率，而实践证明，好算法与指数型时间算法的运算效率有天壤之别。在本模型中，复杂性计算如下：

加法：

比较：

v∈S： （其中为G的顶点数）

总共算得其时间复杂性为O（），是多项式时间算法，即好算法。 此外，我们找到了其它两种算法求最短路径，分别是Floyd算法和Warshall算法。经计算，前者时间复杂性是O（），而后者时间复杂性为O（），二者时间复杂性均大于本模型所选用算法，因此，这种算法的运算速度和运算量目前来说是最优的。

8.2 模型的缺点

由于此题所给地图是闭合的，要求求出从A出发然后绕地球一圈回到A的最短路径，而我们选用的算法只能求出从A到B（A与B为不同地点）的最短路径，因此，在制作关联矩阵时，我们只能将地图从A点截断（即将A分为A和A’）抽象成二维的赋权图G，这里就产生了较为复杂的数据处理问题，因为我们在制作关联矩阵的过程中，需要考虑哪些路应该“截断”（权值设为0），不同的起点需要考虑不同的情况，有不同的关联矩阵，给模型的求解过程带来不便。

另外，用matlab计算出的最短路径编号并不一定和地点编号一一对应，要找出实际路径必须以最短路径编号作为索引在关联矩阵中找到对应地点编号，因为此算法要求起点终点必须在关联矩阵的第一行第一列和最后一行最后一列，并按照关联矩阵的元素位置序号输出路径。但是此缺点带来的工作量可以忽略不计[5]。

8.3 模型的推广

本算法不仅适用于本题环游地球的最短路径求解问题，只要将任何实际问题抽象为赋权图G，并有确定的起点与终点，即可由本算法求出最短路径，最短的时间，最短的路程等等。

实际生活中的许多问题都可归结于图论中的最短路径问题，如：电子导航、交通旅游、公交出行，管道铺设，厂区布局以及电力、通讯中的很多问题等。这里的最短路径不仅仅指地理意义上的距离最短，可引申为最少费用、最短时间、延时最短、吞吐量最大等约束条件。而此模型正是基于典型最短路问题建立的，因此，本文所提供的方法同样适用于解决这些这些问题。

对于一些多阶段决策问题，由于它的特殊性，可将过程分成若干个互相联系的阶段，在其每一阶段都需要作出决策，从而使整个过程达到最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状况，有影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，确定了整个决策过程的活动路线。利用通常的动态规划模型求解是比较困难的，比如，要写出其动态规划的递推关系难度很大，并且不易用程序语言表述，对于此类问题，我们可以将实际问题数学抽象成相应的树图，根据实际情况给图的每一边赋上相应的权值，将它转化为最短路径问题，并利用上述模型求解，这样的转换可简化复杂的动态规划实际问题，并方便地用程序语言进行表达。

此外，基于最短路径问题，我们还可以将本文提出的算法做适当修改，求出最短路径、次短路径等等，这对一些实际问题如交通规划的不同方案选取、旅游路线方案的选取等有重要意义。

九、参考文献

[1]陈东彦等，数学建模，科学出版社

[2]卜月华，图论及其应用，东南大学出版社

[3]章永龙，Dijkstra，最短路径算法优化，南昌工程学院学报，Vol.25，No.3 [4]宋金华，Dijkstra算法程序的优化，海南广播电视大学学，2008，No.4 [5]殷剑宏，图论及其算法，中国科学技术大学出版社

附录

附录一：题目数据图