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

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

顶点呢？如果他们重复，这在 Floyd Warhsall 是否是允许的周期？

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

有人能给我解释一下吗？回答问题，1->2->4->3->4 是否被认为比 1->2->4 更短？？？

提前谢谢大家。

编辑:

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

Answer 1

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