Floyd-Warshall 算法中不允许使用哪种循环？

Question

例如，

让我们说

1->2 costs 100
2->4 costs 600

所以1->2->4成本700

如果从 4 到 3 有一个花费 -500 的边怎么办？以及从 3 到 4 花费 200 的不同边缘

4->3 costs -500
3->4 costs 200

所以1->2->4->3->4成本400

哪个小于 700

所以被1->2->4->3->4认为是比1->2->4???更短的路径

我知道不允许循环，这是没有重复边的路径示例。

顶点呢？如果他们重复，这是 Floyd Warhsall 允许的循环吗？

因为我知道有不同类型的算法，一种允许一种循环而不允许其他类型的循环。

谁可以给我解释一下这个？回答问题，被1->2->4->3->4认为是比1->2->4???更短的路径

谢谢大家。

编辑：

这是一张图片，显示您不必两次访问同一条边。

Answer 1

Floyd\xe2\x80\x93Warshall 算法需要一个没有负循环的图。在您的示例中，4->3->4是一个负循环，因为该循环的权重总和是-500 + 200 = -300。

\n