为什么负边缘在bellman福特算法中允许？

Question

为什么在bellman ford算法中允许负边沿循环，而在dijkstra算法中不允许负边沿？

Answer 1

您所有的问题似乎都是课堂问题。请参阅1.）课本和2.）课堂笔记。你会在1个或两个地方找到明确记录的答案。

Answer 2

允许？ Bellman-Ford算法允许具有负权重的不同边缘（在Dijkstra算法中不支持），但两种算法都不允许“负”周期。最短路径问题在出现负循环时没有意义，因此在任何此类算法中都没有有意义的方法来“允许”负循环。

Bellman-Ford算法可以用来检测是否存在负循环并中止执行（中止，因为在这种情况下不存在正确的解决方案）。