algorithm - 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???更短的路径

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

顶点呢？如果他们重复，这是弗洛伊德沃赫萨尔允许的循环吗？

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

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

谢谢大家。

编辑：

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

Answer 1

Floyd Warshall 是一个有约束的算法：graph with no negative cycle如果你想在一个负循环的图中找到最短路径，你不能使用 Floyd Warshal，这是有理由考虑你的4->3->4带有成本的负循环的图-300。如果您在此周期中进行一次，您的成本会降低到400，700但为什么就止步于此？再去一次，你的成本将是100，一次又一次，它会花费你-200，，-500……。你可以永远这样做，算法永远不会停止。with no negative cycle这就是为什么Floyd Warshall 算法中存在这种约束的原因。

Answer 2

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