負重的Dijkstra算法

Question

現在我知道如果圖形包含負權重邊緣，Dijkstra將不起作用。但是有一個例外。 （只有離開源的邊緣可以具有負的權重，而所有其他邊緣必須是正的。）

我想證明這一點。我不知道如何開始這個。我已經制作了一些圖表，在所有這些Dijkstra中都完美地工作，但我不明白我如何證明這一點？

那麼，其實我是想是有人證明Dijkstra算法會在這種情況下工作或將不會（只有從源頭上輸出邊沿爲負）。

加上圖形不能包含任何循環，其涉及到來源。

Answer 1

首先要注意的是，如果沒有涉及源的循環，我們可以修剪任何到達源的邊的圖，它不會影響結果，在Dijkstra中不會達到通向源的頂點算法（否則，有一個涉及源的週期）。

從現在開始，我們假設沒有傳入邊緣的來源。

注意，如權利要求所需要的鬆弛步驟（三角inequeality）：d(u,v) <= d(u,x) + w(x,v)必須持有（空洞地）針對每個w(x,v) < 0，唯一u其中存在從u到x的路徑（也就是源）是u=x=source，並且路徑是空的路徑。

這導致我們d(u,x) + w(x,v) = 0 + w(x,v) = w(u,v) = d(u,v)（其中u是來源），並且不等式仍然成立。

Answer 2

您可以簡單地將通用初始實例D轉換爲可行實例D'（即只包含正邊值），然後顯示Dijkstra算法在兩個實例上的行爲相同。從這裏就可以得出結論，Dijkstra算法是正確的

以下D.

形式的實例是詳細信息：

您轉換d至d」通過插入一個‘超級源’S'它只有一個邊 - 對於距離d（s'，s）= -min {d（s，x）| x是一個節點}的輸出。這個例子相當於把s（s'，s）加到s的所有輸出邊上，我們稱之爲D'。它只有正邊緣權重。

Dijkstra算法在D和D'上的行爲與隊列中距離的排序保持不變，因此相同的節點由相同（移位）的距離等來確定。請注意，在此參數中我們隱含地使用不存在包含s的（負）循環。

因爲我們知道D'的Dijkstra算法找到變換圖的正確距離，並且D和D'的最短路徑的結構必須相同，我們可以得出結論：Dijkstra算法的D是正確的。

注意：您始終可以使用所謂的Johnson Shift來讓Dijkstra算法在沒有負循環的圖上正確執行。您也可以使用Johnson Shift作爲證明，但這不會是自包含的。