爲什麼負邊緣在bellman福特算法中允許？

Question

爲什麼在bellman ford算法中允許負邊沿循環，而在dijkstra算法中不允許負邊沿？

Answer 1

您所有的問題似乎都是課堂問題。請參閱1.）課本和2.）課堂筆記。你會在1個或兩個地方找到明確記錄的答案。

Answer 2

允許？ Bellman-Ford算法允許具有負權重的不同邊緣（在Dijkstra算法中不支持），但兩種算法都不允許「負」週期。最短路徑問題在出現負循環時沒有意義，因此在任何此類算法中都沒有有意義的方法來「允許」負循環。

Bellman-Ford算法可以用來檢測是否存在負循環並中止執行（中止，因爲在這種情況下不存在正確的解決方案）。