algorithm - 为什么在 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) 中完成。