最短路径的floyd算法的时间复杂度

31... 31 展开
 我来答
xl3303
2022-09-24 · 超过147用户采纳过TA的回答
知道小有建树答主
回答量:416
采纳率:100%
帮助的人:16.8万
展开全部

Floyd:每对节点之间的最短路径。Floyd-Warshall算法(Floyd-Warshall
   algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。

Dijkstra: O(n2) 适用于 权值为非负 的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV),

BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE)

SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(VE).

先给出结论:

(1)当权值为非负时,用Dijkstra。

(2)当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈。

(3)当权值有负值,而且可能存在负圈,则用BellmanFord,能够检测并输出负圈。

(4)SPFA检测负环:当存在一个点入队大于等于V次,则有负环,后面有证明。

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式