最短路径算法

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

1、最短路径算法最短路径问题在 GIS、CS、OR 等学科中一贯被广泛地进行研究。最短路径 问题一般分为单源与多源两种，单源被广泛的使用较多地用于解决实际问题，例 如在资源分配、线路规划等优化上有着不可替代的作用。在前人对单源最短路径问题的研究中，已经有很多经典的算法被提出用于解 决该问题，例如Dijkstra、Bellman-Ford、A*等算法。这些不同的算法对于不同 的图、应用需求以及软硬件条件，在时间复杂度、空间复杂度、易用性方面各有 长处。下面介绍下几种经典的求解最短路径问题方法,Dijkstra算法、A*算法、Floyd 算法，其中Floyd算法用于解决多源问题。1、 Dijkstra

2、 算法Dijkstra算法(DA)是最有用和最有效的图搜索算法之一，可以对其进行修 改以解决许多不同的问题。它通常作为查找映射的工具呈现，该映射对于每个顶 点e，从固定的单个源顶点返回到e的最短路径。算法的主要思想是把起点作为 中心，距离增加的同时向中心外围进行扩张，一直扩张到达终点结束计算 52。 但是如果路径中有权值为负数，则无法找到一条最优路径。权值无负数的有向图G = (V,E)，顶点e .与顶点e .之间的用表示弧, 弧的权值为w 。顶点x、y e V， P = e = x,e = e = y表示联通x i j ab 0 1 n 到y路径的顶点集合，W(P J为路径中所有权值相加的结

3、果，如式(2.3)所示。abW(P ) = 0 w (2.3)ab i ji=1Dijkstra 算法如表 2.1 所示，由于算法的实现比较经典，故仅做简单伪代码 描述。首先从初始化开始，源点的距离初始化为0源点的前驱为null，其他所 有顶点前驱为null，并且其他顶点到源点的距离无穷大；然后进行构造堆，顶点 按距离属性构造最小堆；最后只要堆中还存在元素就一直在循环中，删除堆顶元 素，该元素记为v,寻找v的所有邻接点，更新v所有的邻接点的距离。表 2.1 Djjkstra 算法算法：Dijkstra算法输入：非负有向图G(V,E)，每条边的权w(u,v)，源点s输出：最短路径顶点集合S1:初

4、始化2:构造堆(Q = V(G)3:while (!isEmpty(Q)4:v = EXTRACT-MIN(Q)5:for each vertex v_adj belongs to Adjv6:更新v的邻接点v adj2、A*算法通过将广度优先遍历算法与 Dijkstra 算法的组合，使算法在进行最优解的寻找的过程中避免向不含最优解的方向寻找，而是从一开始就往最优解方向寻找解算法伪代码如表2.2所示。表2.2 A*算法算法:A*算法1:OPEN = starting2:CLOSE = null3:while(OPEN != null)4:A = MING(OPEN);5:if(ending=A)6:break;7:else 8:for(each X connected with A) 9:if(X in CLOSE)10:continue;11:else 12:if(g(n) + g(n,x) D( ,e ) + D( ,e )，则用两段路径代替原来 i k k j i j i k k j的路径，并更新矩阵D (k)；3) 计算所有顶点后，得到最终的邻接矩阵。该算法思想较易，并可以计算任意两点间的最短距离，但是时间复杂度为O ( “ 3)，不适合用作大数据量的移动污染源时空轨迹序列数据。