爲什麼Dijkstra算法需要使用deleteMin（）和decreaseKey（）？

在大多數件僞的，我通常會發現以下幾點：（具有最小鍵返回元素，並從集合刪除）爲什麼Dijkstra算法需要使用deleteMin（）和decreaseKey（）？

DeleteMin

DecreaseKey（容納下降在一個特定的元素的鍵的值）

2012-06-21 fdh

你是在談論[heap]（http://en.wikipedia.org/wiki/Heap_（data_structure）），而不是Dijkstra的算法？ –

可能的重複[爲什麼Dijkstra的算法使用遞歸鍵？]（http://stackoverflow.com/questions/9255620/why-does-dijkstras-algorithm-use-decrease-key） –

如果你把一個隨機的下一個節點（不是最小距離）算法不正確。 –

爲什麼DeleteMin被用於檢索的最小元素 - 爲什麼不一個隨機？

我們檢索和Q刪除分鐘元素集合開放的頂點，因爲它保證極小（後來在證明中使用）。沒有它 - 最低限度的功能不能保證，解決方案將不是最優的（不會是最短的路徑）。請記住，一旦我們找到了v的路徑，我們將它從Q中刪除，並且永遠不會重新打開它，因此我們拿出的邊緣必須具有可用路徑最小的路徑。

注意，對於這（最小）頂點，讓它成爲v：對於每個u在Qd(u) + x <= d(v) - 因爲Dijkstra算法時沒有負邊緣中，x> = 0時使用。
對於任何其他頂點 - 這不是最小的 - 我們不能保證沒有更短的路徑尚未被發現。

DecreaseKey的用途是什麼？在僞代碼中，一個元素的值被改變後，它總是被稱爲。它在做什麼？

使用減少是因爲我們可能找到了一條新的更好的路徑來連接到我們找到的最後一個頂點。 這一步是dijkstra算法的放鬆步驟。請記住，dijkstra的算法始終保持到每個頂點到目前爲止找到的最短路徑，因爲最後一步可能找到了到某個頂點的新的最短路徑 - 此步驟正在更新到目前爲止發現的最短路徑。

2012-06-21 11:52:37 amit

謝謝，這非常有幫助！ – fdh

回答