最短路径算法最短路径问题在 GIS 、CS、OR 等学科中一贯被广泛地进行研究。最短路径问题一般分为单源与多源两种，单源被广泛的使用较多地用于解决实际问题，例如在资源分配、线路规划等优化上有着不可替代的作用。在前人对单源最短路径问题的研究中，已经有很多经典的算法被提出用于解决该问题，例如Dijkstra 、Bellman-Ford 、A*等算法。这些不同的算法对于不同的图、应用需求以及软硬件条件，在时间复杂度、空间复杂度、易用性方面各有长处。下面介绍下几种经典的求解最短路径问题方法，Dijkstra 算法、 A*算法、 Floyd 算法，其中 Floyd 算法用于解决多源问题。1、Dijkstra 算法Dijkstra 算法( DA ) 是最有用和最有效的图搜索算法之一，可以对其进行修改以解决许多不同的问题。它通常作为查找映射的工具呈现，该映射对于每个顶点 v，从固定的单个源顶点返回到v 的最短路径。算法的主要思想是把起点作为中心，距离增加的同时向中心外围进行扩张，一直扩张到达终点结束计算[52]。但是如果路径中有权值为负数，则无法找到一条最优路径。权值无负数的有向图G (V,E) ，顶点 Vi 与顶点 V j之间的用 vi,vj 表示弧 , 弧的权值为w v i ,vj 。顶点 x、y V ， P ab {v 0 x, v 1 ..., v n y}表示联通 x 到 y 路径的顶点集合， W( PaJ 为路径中所有权值相加的结果，如式( 2.3) 所示。n 1 W(P ab) w v* ( 2.3)i 1 Dijkstra 算法如表 2.1 所示，由于算法的实现比较经典， 故仅做简单伪代码描述。首先从初始化开始，源点的距离初始化为0，源点的前驱为 null，其他所有顶点前驱为 null, 并且其他顶点到源点的距离无穷大；然后进行构造堆，顶点按距离属性构造最小堆；最后只要堆中还存在元素就一直在循环中，删除堆顶元素，该元素记为 v, 寻找 v 的所有邻接点，更新v 所有的邻接点的距离。表 2.1 Dijkstra 算法算法： Dijkstra 算法输入：非负有向图G(V,E) ，每条边的权 w(u,v) >0 , 源点 s输出：最短路径顶点集合S1:初始化2:构造堆 (Q = V(G)) 3:while (!isEmpty(Q)) 4:5:6:v = EXTRACT -MIN(Q)for each vertex v_adj bel ongs to Adj[v] 更新 v 的邻接点 v adj2、 A*算法通过将广度优先遍历算法与Dijkstra 算法的组合，使算法在进行最优解的寻找的过程中避免向不含最优解的方向寻找，而是从一开始就往最优解方向寻找解。算法伪代码如表 2.2 ...
