我是靠谱客的博主 会撒娇羽毛,这篇文章主要介绍最短路径算法复杂度总结,现在分享给大家,希望可以做个参考。

Dijkstra:O(n2)适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV),
BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE)
SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(VE).
Floyd:每对节点之间的最短路径。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。

先给出结论:
(1)当权值为非负时,用Dijkstra。
(2)当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈。
(3)当权值有负值,而且可能存在负圈,则用BellmanFord,能够检测并输出负圈。
(4)SPFA检测负环:当存在一个点入队大于等于V次,则有负环,后面有证明。

原文地址:http://blog.csdn.net/basycia/article/details/50766436

最后

以上就是会撒娇羽毛最近收集整理的关于最短路径算法复杂度总结的全部内容,更多相关最短路径算法复杂度总结内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部