如何獲得具有負重量循環圖的單源最短路徑

Question

嘿，我一直在研究「單源最短路徑」問題的bellman ford算法。

現在我被困在一個點，我需要找出負重量循環圖的解決方案。

但Bellman ford算法在這裏不起作用。

有人可以建議我該怎麼做。如何解決負重量循環的問題？

謝謝你的時間。

Answer 1

如果有一個從原點到達的負循環，Bellman-Ford可以檢測到，那麼您有兩個選擇：允許重複邊或不重複。如果你允許重複邊緣，你的最短路徑可以被認爲是無限的。否則，如果你不這樣做，問題是NP完成。從Wikipedia：

最短路徑問題的一個NP-Complete變體要求G中的最短路徑（包含負循環），以便不重複邊沿。