几大最短路径算法比较
July、二零一一年二月十二日。
-----------------------------------
几个最短路径算法的比较:
Floyd
求多源、无负权边的最短路。用矩阵记录图。时效性较差,时间复杂度O(V^3)。
Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题。
Floyd-Warshall算法的时间复杂度为O(N^3),空间复杂度为O(N^2)。
Floyd-Warshall的原理是动态规划:
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k,则Di,j,k = Di,k,k-1 + Dk,j,k-1;
若最短路径不经过点k,则Di,j,k = Di,j,k-1。
因此,Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。
在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。
Floyd-Warshall算法的描述如下:
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then
Di,j ← Di,k + Dk,j;
其中Di,j表示由点i到点j的代价,当Di,j为 ∞ 表示两点之间没有任何连接。
Dijkstra
求单源、无负权的最短路。时效性较好,时间复杂度为O(V*V+E)。
源点可达的话,O(V*lgV+E*lgV)=>O(E*lgV)。
当是稀疏图的情况时,此时E=V*V/lgV,所以算法的时间复杂度可为O(V^2) 。若是斐波那契堆作优先队列的话,算法时间复杂度,则为O(V*lgV + E)。
更多,请参考:二(续)、彻底理解Dijkstra算法,及二(再续)、Dijkstra 算法+fibonacci堆的逐步c实现。
Bellman-Ford
求单源最短路,可以判断有无负权回路(若有,则不存在最短路),
时效性较好,时间复杂度O(VE)。此算法日后还会在本BLOG内具体阐述。
Bellman-Ford算法是求解单源最短路径问题的一种算法。
单源点的最短路径问题是指:
给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。
与Dijkstra算法不同的是,在Bellman-Ford算法中,边的权值可以为负数。
设想从我们可以从图中找到一个环路(即从v出发,经过若干个点之后又回到v)且这个环路中所有边的权值之和为负。那么通过这个环路,环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。
SPFA
是Bellman-Ford的队列优化,时效性相对好,时间复杂度O(kE)。(k<<V)。
与Bellman-ford算法类似,SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是,SPFA算法通过维护一个队列,使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点,从而大大减少了重复的操作次数。
SPFA算法可以用于存在负数边权的图,这与dijkstra算法是不同的。
与Dijkstra算法与Bellman-ford算法都不同,SPFA的算法时间效率是不稳定的,即它对于不同的图所需要的时间有很大的差别。
在最好情形下,每一个节点都只入队一次,则算法实际上变为广度优先遍历,其时间复杂度仅为O(E)。另一方面,存在这样的例子,使得每一个节点都被入队(V-1)次,此时算法退化为Bellman-ford算法,其时间复杂度为O(VE)。
SPFA算法在负边权图上可以完全取代Bellman-ford算法,另外在稀疏图中也表现良好。但是在非负边权图中,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法,以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。
完。
分享到:
相关推荐
单源最短路径(SPFA) Bellman-Ford(Queue-Optimised) 单源最短路径(Bellman-Ford) Bellman-Ford 使用Edmonds-Karp进行二分图匹配 Bigrpah-Matching(Edmonds-Karp) 普通的二叉搜索树 Binary-Search-Tree 广度...
这是我个人的技术采访资料集。 演算法 数组相关 核心 快速选择LC1471 彩虹排序 字符串匹配 核心 ... 最短路径更快算法(SPFA) LC743 在Bellman-Ford之上的改进 约翰逊算法 基数排序 联合发现LC
Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 插入排序 选择排序 希尔排序 堆排序 快排 归并排序 线性排序算法基数排序 查找算法 顺序表查找:顺序查找 有序表查找:二分查找 分块...
leetcode 和 oj 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序
leetcode算法题主函数如何写 算法虐我千百遍,我待算法...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查
leetcode 和 oj 算法虐我千百遍,我待算法如...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序
leetcode 和 oj 算法虐我千百遍,我待算法如...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序
leetcode中国 #The file is in Chinese 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入
leetcode中国 #The file is in Chinese 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入
leetcode ...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 快排 堆排序 希尔排序 归并排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序查找 有序表查找:二分
leetcode 和 oj 算法虐我千百遍,我待算法如...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序
leetcode 和 oj 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排
leetcode中国 #The file is in Chinese 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入
Bellman-Ford, SPFA, Floyd : 染色法、匈牙利算法 数学知识 其他 LeetCode分类复习清单 Greedy Assignments: , Intervals: [452 Disjoint Interval], DFS / Backtracing [22 Parentheses], [46 Permutation], , [77 ...
Floyd,Dijkstra,bellman-ford,SPFA,A* Knuth-Morris-Pratt Boyer-Moore 参考资料 基础 《算法导论》 《Algorithms》 面试算法 《剑指offer》 《编程之美》 延伸阅读 《深入理解计算机系统》 《计算机程序的构造和...
最短路径优先算法 SPFA 网络流 最大流:Ford&Fulkerson算法 最大流:Dinic算法 最大流:ek算法 最大流:dsp算法 最大流:hlpp算法 最小费用最大流:bellman_ford找增广路 最小费用最大流:ssp算法 字符串 ...
Bellman-Ford 1.6.2.1.1.2.1. Shortest path faster algorithm(SPFA) 1.6.2.1.2. 应用Applications 1.6.2.1.2.1. 差分约束系统 System of difference constraints 1.6.2.1.2.2. 有向无环图上的最短路 Shortest ...
1.6.2.1.1.2. Bellman-Ford 1.6.2.1.1.2.1. Shortest path faster algorithm(SPFA) 1.6.2.1.2. 应用Applications 1.6.2.1.2.1. 差分约束系统 System of difference constraints 1.6.2.1.2.2. 有向无环图上的最短路 ...