有人可以幫我解決這個問題嗎
我仍然很困惑 Dijkstra 的演算法是否適用于負邊緣
這個問題來自 Grokking Algorithms 書，在其勘誤表中據說這個問題有一個可能的答案
它如何有一個可能的答案負邊緣？
uj5u.com熱心網友回復：
首先，Dijkstra 的演算法不適用于所有負權重圖，但在這種特殊情況下，您可以看到負權重在從起點到圖上任何其他點的最短路徑上沒有任何不同。這就是為什么無論有沒有負邊緣你都會得到相同的結果。
這里很好地解釋了為什么 Dijkstra 不能處理負權重圖的想法（感謝 Amit）->為什么 Dijkstra 的演算法不能處理負權重邊？
uj5u.com熱心網友回復：
我上次接觸 Dijkstra 已經有 10 年了，但我認為這個不會中斷，因為每次越過負部分時，回圈仍然增加總和（減 1 對幾個加 2）。這樣，帶有否定的路徑被丟棄。但是將負 1 更改為負 5，然后您就會遇到問題。
我現在不在我的電腦上將這個圖表應用到我 10 歲的家庭作業中，但我很確定這就是正在發生的事情。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359109.html
上一篇：斐波那契記憶回傳串列從0到N