请问BellmanFord算法判断负权环是否也可以使用和Floyed一样的方法？

首页课程实战体系课手记专栏慕课教程

请问BellmanFord算法判断负权环是否也可以使用和Floyed一样的方法？

来源：12-8 负权环

martin123_

2019-10-04

如题

写回答

1回答

liuyubobobo

liuyubobobo

2019-10-04

不可以。因为 Bellman-Ford 是单源最短路径，只是从一个源点出发。所以直接看 dis[s][s] 是否是负数，只能看出来有没有通过 s 的负权环。但是一个负权环可以不通过 s。

但是对于 floyd 算法来说，由于求的是所有点对最短路径，而一个负权环肯定通过某一个点，所以检查所有的 dis[v][v] 是有效的。

继续加油。

0

3

martin123_

回复

liuyubobobo

好吧，前面笔误了；应该理解了，感谢

2019-10-04

共3条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

相似问题

求TSP问题的算法

回答 1

老师您好，关于实际生产环境中DFS实现的问题

回答 1

关于有向图的数据结构（实现）

回答 1

负权边和负权环

回答 1

图的dfs非递归算法性能效率如何？

回答 1

打开慕课网App查看更多内容