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

Question

如题

Answer 1

liuyubobobo 2019-10-04 14:54:37

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

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

继续加油。

• 提问者 martin123_ #1

  能不能粗略地这么理解：假如在无向图中某条负权边绝对值较小，从而导致一个从原点出发经过这条负权边再次到达原点的环的消耗仍为正数，所以直接判断dis[s] == 0不正确？

• liuyubobobo 回复 提问者 martin123_ #2

  没有特别理解你的意思。首先，对于无向图，只要有一条负权边，就存在负权环了；其次，为什么是判断 dis[s] == 0？直接判断 dis[s] < 0 不正确。因为 dis[s] < 0 只意味着有一条经过 s 的负权环。但整个图可以有不经过 s 的负权环。

• 提问者 martin123_ 回复 liuyubobobo #3

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