0

为什么贝尔曼福特算法允许负边缘循环，而迪杰斯特拉算法不允许负边缘循环？

4

1 回答 1

6

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

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

于 2010-11-29T18:57:40.780 回答