爲什麼Dial版本的Dijkstra算法中使用雙鏈表？

Question

我見過的幾篇論文和幻燈片提到Dial的Dijkstra單源最短路徑算法的實現。他們都說一個桶被存儲爲一個雙向鏈表。 （例如，http://www.cs.ucsb.edu/~suri/cs231/ShortestPaths.pdf,http://www.acsu.buffalo.edu/~nagi/courses/684/4.shortestpath.pdf）。然而，所需的操作僅僅是這樣（就我看到的）：

1. 察看剷鬥空

2. 將節點添加到一個桶（順序並不重要）

3. 在刪除傳遞的節點時對一個存儲桶進行迭代。

他們都可以用一個單向鏈表來完成一樣容易（2，只是改變指針列表到新節點的開始，它的下一個指針更改爲老第一個節點在桶裏）。

那麼，有沒有一個原因，我錯過了爲什麼雙向鏈表是理想的呢？

Answer 1

我想通了。我錯過的操作是，當我們迭代一個桶時，我們需要移動鄰居頂點，從而從其他桶中刪除它們的節點。這可以在雙鏈表中的O(1)和單鏈表中的O(size of bucket)中完成。