最短路算法:最短路径算法是图论研究中,一个经典算法问题;旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
确定起点的最短路径问题:已知起始点,求最短路径问题。适合使用Dijkstra算法;(单源最短路径问题)
全局最短路径问题:求图中所有的最短路径,适用于Floyed-Warshall 算法;(多源最短路径问题)
单源最短路径:给定一个带权有向图G=V,E; 其中每条边是一个实数。另外,还给定V中的一个顶点,称为源;要计算从源到其他所有顶点的最短路径长度。这个长度是指路上各边权之和。这个问题通常称为单源最短路径问题;
Dijkstra算法:Dijkstra算法使用的是贪心的思想,即在问题求解是总是选择当前最优解;该算法用于求解单源最短路问题,不能处理负权,只能用于正权图中;算法使用贪心策略,从s0开始,选择未访问过vi的离s0最近的一个点i,也就是最小的di;然后将i作为中间点,更新经过i,可以到达的点的最短路距离,继续贪心寻找未访问过的最近的一个点,经过n次贪心,所有的点访问完毕,算法结束;输出起点和终点间的最短路距离;
Floyed算法:Floyed算法,又称为插点法,一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法;该算法可以求出多源最短路,可以处理负权边情况,但是不能出现负环;该算法思想使用动态规划思想;
Bellman-Ford算法:贝尔曼福特算法是一种单源最短路算法;它相对Dijkstra算法可以进行处理负权,适用前提:没有负环;实现简单,但是时间复杂度高;可以用来判断是否存在负环,每次迭代更新起点到各节点的最短路径;如果迭代n-1次后(6个点之间存在n-1条边),再次迭代还有路径更新,则说明存在负环;
算法思想:图的任意一个条最短路,既不会包含负权回路,也不会包含正权回路,最多包含n-1边。那么,从源点s开始,可以达到的节点,如果存在最短路,则最短路构成了一颗以s为根的最短路树。因此,可以按照距离根s的层次,逐层生成达到每个点的最短路(松弛操作);所以整个过程,就是创建最短路树的过程;需要一个辅助数组dn和vn来记录最短路距离和跟踪寻迹;从边的角度来考虑,每次迭代要遍历每条边;循环n-1次后,第n次循环如果所有dn值不更新,则跳出循环;如果第n次还存在路径更新,则说明存在负环;Bellman-Ford算法也可以求解最长路和用来判断正环,只要在递推关系选择最大的更新就好;
算法实现过程:
SPFA算法:SPFA(Shortest Path Faster Algorithm);上面描述的Bellman-Ford算法,算法时间复杂度比较高;Bellman-Ford算法需要递推n次,每次递推需要扫描所有的边;然而每次松弛操作并不需要对所有的边松弛,只需要与当前找到最短路的点相连的边进行松弛;所以使用队列,每次将距离更新且不在队列中的点入队;每次从队列中取出一个顶点,对它所有相邻的节点进行松弛,如果某个顶点松弛成功,如归该点不在队列中,则将其入队,重复这样的操作,直到队列为空为止;如果一个节点入队次数超过n次,说明存在负权回路;可以使用一个cntn数组来进行计数;
算法实现过程:
时间复杂度分析:
代码实现请参考:https://github.com/yaowenxu/codes/tree/master/最短路算法
保持更新,转载请注明出处;更多内容请关注cnblogs.com/xuyaowen;
参考文献:
最短路问题 四种最短路算法 dijkstra算法 Floyd算法 Prim与Dijkstra算法的区别 Bellman-Ford算法 SPFA算法