如何更新Dijkstra算法中鬆弛頂點的密鑰？

Question

就像有人問here， 我不明白，我們怎麼能找到在堆輕鬆頂點的索引。

編程風格明智的，heap是一個黑箱抽象掉優先級隊列的細節。現在，如果我們需要維護一個將頂點鍵映射到堆數組中相應索引的散列表，那需要在heap實現中完成，對吧？

但是大多數標準堆並不提供這樣的映射的散列表。

另一種方式來處理這個問題，全是輕鬆的頂點添加到堆不顧一切。當我們提取最小值時，我們會得到最好的一個。爲了防止多次提取同一個頂點，我們可以標記它訪問了。

所以我確切的問題是，典型的（在業內）處理這個問題的方式是什麼？

比較我提到的方法有哪些優缺點？

Answer 1

你問一些非常有效的問題，但不幸的是他們都是那種模糊的，所以我們不能給你一個100％固體「行業標準」的答案。不過，我會盡力去超過你的觀點呢：

編程風格明智的，堆是一個黑箱抽象掉優先級隊列的細節

從技術上講，優先隊列是抽象接口（插入具有優先級的元素，提取最低優先級的元素），堆是具體實現（基於數組的堆，二項堆，斐波那契堆等）。

我想說的是，使用數組只是實現優先級隊列的一種特殊方式。

現在，如果我們需要維護一個散列表，它將頂點鍵映射到堆數組中的相應索引，那麼這需要在堆實現中完成，對吧？

是的，因爲每次移動數組內的元素時，都需要更新散列表中的索引。

但是大多數標準堆並不提供這樣的映射的散列表。

是。這可能非常煩人。

解決這個問題的另一種方法是無論任何事情，都可以將放鬆的頂點添加到堆中。

我想這可以工作，但我不認爲我見過任何人這樣做。在這裏使用堆的關鍵是要提高性能，並在堆中添加多餘的元素，這是違背它的。當然，你保留優先隊列的「黑盒子」，但我不知道這是否值得。另外，額外的pop_heap操作可能會對你的漸近複雜性產生負面影響，但我不得不做數學檢查。

處理這個問題的典型方法是什麼？

首先，問問自己是否可以使用啞數組而不是優先級隊列。 當然，現在找到O（N）中的最小元素而不是O（log n），但實現是最簡單的（本身就是一個優點）。此外，如果圖形密集，並且即使圖形稀疏，使用數組效果也會一樣高，這取決於圖形的大小。

如果你確實需要一個優先級隊列，那麼你將不得不找到一個執行了reduceKey操作的隊列。如果你找不到它，我會說它自己實現它並不壞 - 它可能比試圖找到一個現有的實現然後試圖使其與其他代碼相適應更麻煩。

最後，我會不是建議使用真正的花式堆數據結構（如斐波那契堆）。雖然這些經常出現在教科書中作爲獲得最佳漸近線的方法，但實際上它們具有可怕的常數因子，與對數相比，這些常數因子是顯着的。

Answer 2

編程風格上，堆是一個黑盒子，它抽象出優先級隊列的細節。

不一定。 C++和Python都有堆庫，它們在數組上提供函數而不是黑箱對象。 Go抽象了一點，但要求程序員爲其堆操作提供一個類似數組的數據結構。

所有這些抽象的標準化，產業實力庫泄漏是有原因的：一些算法（Dijkstra算法）需要額外的操作，這會降低其他算法的性能堆。然而其他算法（堆排序）需要在輸入陣列上就地工作的堆操作。如果你的圖書館的堆給你一個黑盒子對象，並且它不能滿足某些算法，那麼是時候重新實現操作作爲數組的函數，或者找到一個具有你需要的操作的庫。

Answer 3

通常情況下，你需要的是支持，爲了得到這個工作的decreaseKey操作的特殊構造的優先級隊列。我已經看到這通過讓優先級隊列明確跟蹤索引的哈希表（如果使用二進制堆）或通過具有入侵優先級隊列（其中存儲的元素是堆中的節點）來實現的（如果使用二項堆或Fibonacci堆，例如）。有時，優先級隊列的插入操作會返回一個指向保存新添加的密鑰的優先級隊列中的節點的指針。作爲一個例子，這裏是一個支持decreaseKey的implementation of a Fibonacci heap。它通過讓每個插入操作返回一個指向Fibonacci堆中節點的指針來工作，這使得可以在O（1）中查找節點，假設您跟蹤返回的指針。

希望這會有所幫助！