我可以在圖中使用Dijkstra的最短路徑算法嗎？

Question

我有一個有向圖，除了離開源（S）的邊之外，它有所有非負邊。從源的任何其他頂點都沒有邊。要找到圖中源（S）到頂點（T）的最短距離，即使離開源的邊是負數，我也可以使用Dijkstra的最短路徑算法嗎？

Answer 1

假設只有源面 - 邊緣邊緣可以具有負權重，並且沒有路徑從任何源面 - 節點節點返回到源面（如註釋中所述），則可以在所有邊緣上添加常量C來源使它們都是非負面的。然後從最終結果中減去C。

在更一般的說明中，在應用Johnson's reweighting algorithm（本質上是Bellman-Ford，但需要僅執行一次）之後，Dijkstra可用於解決任何具有負邊權重（但無負循環）的圖中的最短路徑）。

Answer 2

你一般不能將Dijkstra算法用於帶有負向鏈接的（有向）圖的原因是Dijkstra的算法很貪婪。它假設一旦你選擇一個最小距離的頂點，就沒有辦法通過更小的路徑到達以後的。

在您的特定圖形中，在第一步之後，您將遍歷所有可能的負邊，並且從現在開始Dijkstra的假設實際上保持不變。無論現在直接連接的頂點現在具有負值，一旦確定哪個頂點具有最小距離，就再也無法以更小的距離再次到達頂點（因爲從此點開始遍歷的所有邊將具有正值距離）。

Answer 3

是的，您可以在該類型的有向圖上使用Dijkstra。

如果您已經完成了對Dijsktra的alghoritm並且它不能使用負值，那麼找到最低的負邊並將該數添加到所有起始邊是一種很好的做法，因此根本沒有負數。完成後你減去這個數字。如果你自己編碼（這非常簡單，我推薦給你），你幾乎不會改變任何東西，只需從最低值開始（像Dijkstra一樣）並允許它，最低值可以是負。它會在你的情況下工作。

Answer 4

如果您考慮dijkstra的算法將算法放在邊緣以使算法工作的條件，那麼只有在初始化後它們永遠不會減少。

因此，如果第一步是負數，那麼實際上並不重要，因爲從這幾個點開始，函數會不斷增加，從而找到正確的輸出（如果沒有辦法返回起始平方）。