为什么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，只需将指针更改为列表开头的新节点，并将其下一个指针更改为桶中旧的第一个节点）。

那么，我错过了为什么需要双向链表的原因吗？

- Alexey Romanov

Answer 1

我明白了。我错过的操作是，在我们迭代一个桶时，我们需要移动相邻的顶点，并从其他桶中删除它们的节点。这可以在双向链表中以O(1)的时间复杂度完成，在单向链表中则需要O(bucket大小)的时间复杂度。

- Alexey Romanov