《2022年五大最短路径算法比较 .pdf》由会员分享，可在线阅读，更多相关《2022年五大最短路径算法比较 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、五大最短路径算法比较July 、二零一一年二月十二日。本文参考：维基百科。- 几个最短路径算法的比较：I 、 Floyd： 求多源、无负权边的最短路。 用矩阵记录图。 时效性较差， 时间复杂度O(V3)。Floyd-Warshall算法（ Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。Floyd-Warshall的原理是动态规划：设 Di,j,k为从 i 到 j 的只以 (1.k)集合中的节点为中间节点的最短路径的长度。若最短路径经
2、过点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 O（E*lgV ）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V2） 。若是斐波那契堆作
3、优先队列的话，算法时间复杂度，则为O（V*lgV + E）。更多，请参考：经典算法研究系列：二、Dijkstra 算法http:/ 求单源最短路， 可以判断有无负权回路（若有，则不存在最短路） ，时效性较好，时间复杂度O（VE）。 此算法日后还会在本BLOG 内具体阐述 。Bellman-Ford算法是求解单源最短路径问题的一种算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 单源点的最短路径问题是指：给定一个加权有向图G
4、和源点 s，对于图G 中的任意一点v，求从 s 到 v 的最短路径。与 Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从 v 出发， 经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路， 环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。而 Bellman-Ford算法具有分辨这种负环路的能力。IV 、 SPFA ： 是 Bellman-Ford的队列优化， 时效性相对好， 时间复杂度O （kE ） 。（kV） 。与 Bellman-ford算法类似， SPF
5、A 算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA 算法通过 维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。SPFA 算法可以用于存在负数边权的图，这与dijkstra算法是不同的。与 Dijkstra算法与 Bellman-ford算法 都不同，SPFA 的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。在最好情形下， 每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为 O(E) 。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)
6、 次，此时算法退化为 Bellman-ford算法，其时间复杂度为O(VE) 。SPFA 算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA 算法在一类网格图中的表现不尽如人意。V、宽搜 ：求单源无权最短路。矩阵记录法时间复杂度O(V2)；边表记录法时间复杂度O(kE) 。第三名： BFPRT 算法1973 年，Blum 、Floyd 、Pratt 、Rivest 、Tarjan集体出动， 合写了一篇题为“ Time bounds f
7、or selection” 的论文，给出了一种在数组中选出第k 大元素的算法，俗称中位数之中位数算法。依靠一种精心设计的pivot 选取方法， 该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏O(n2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于骨掌股掌之间，构造出了一个当之无愧的来自圣经的算法。我在这里简单介绍下在数组中选出第k 大元素的时间复杂度为O（N）的算法：类似快排中的分割算法：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3
8、页 - - - - - - - - - 每次分割后都能返回枢纽点在数组中的位置s, 然后比较s 与 k 的大小若大的话，则再次递归划分arrays.n，小的话，就递归arrayleft.s-1 /s为中间枢纽点元素。否则返回 arrays，就是 partition中返回的值。/ 就是要找到这个s。找到符合要求的s 值后，再遍历输出比s 小的那一边的元素。各位可参考在：算法导论上，第九章中，以期望线性时间做选择，一节中，我找到了这个寻找数组中第k 小的元素的，平均时间复杂度为O（N）的证明：上述程序的期望运行时间，最后证明可得O(n) ，且假定元素是不同的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -