爲什麼Dijkstra的算法必須在每一輪中提取min？

Question

考慮圖形是有效的用於施加Dijkstra算法即沒有負邊緣的權重。我很難說服自己，只有選擇每一輪中的最小距離節點進行提取時，Dijkstra算法纔有效。什麼構成一個證明，除了最小距離節點之外的任何東西都會導致Dijkstra算法的失敗？ 我在尋找一個很好的論點，但支持的例子是受歡迎的。

Answer 1

如果提取非最小的節點，那麼你將已提取的量，最短距離不提取時已知的節點。它將在稍後計算，但節點不會再次被提取，所以在最後至少會留下一個錯誤的最小距離。

例子：

您將有d[1] = 0，那麼你會因爲它是唯一一個提取提取此。

這將設置：

d[3] = 3 
d[2] = 1 

現在你應該提取2，但假設您提取3。

您將設置d[4] = 4。

現在讓我們假設你提取2並設置d[3] = 2。

接着，僅4留給被提取。你提取它，你就完成了。

你留下

與d[4] = 4代替d[4] = 3一個錯誤的值。

請注意，這假定您不能多次提取節點（在經典的Dijkstra算法中不能這樣做）。如果你允許這樣做，那麼你的建議確實有效，但可以說是既不高效也不是Dijkstra的。