为什么Dijkstra算法要使用减小关键字（decrease-key）？

Question

我学习的迪杰斯特拉算法如下所示

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

但是我已经阅读了一些与该算法相关的内容，许多版本我看到都使用decrease-key而不是insert。

为什么会这样，以及这两种方法之间有什么区别？

- weeb

---

Downvoter- 你能否解释一下这个问题有什么问题吗？我认为它非常公正，而且很多人（包括我）最初接触的是 OP 版本的 Dijkstra 算法，而不是 decrease-key 版本。 - templatetypedef

Answer 1

使用 decrease-key 而不是重新插入节点的原因是为了保持优先队列中节点数量的少，从而保持总优先队列出队操作的少和每个优先队列平衡的成本低。

在 Dijkstra 算法的实现中，如果将节点与它们的新优先级重新插入到优先队列中，则对于图中的每个 m 条边都会添加一个节点到优先队列中。这意味着在优先队列上有 m 个入队操作和 m 个出队操作，给出了总运行时间 O(m T_e + m T_d)，其中 T_e 是将元素入队到优先队列所需的时间，T_d 是从优先队列中取出元素所需的时间。

在支持降低关键字的Dijkstra算法实现中，持有节点的优先队列起始时有n个节点，并且在算法的每个步骤中移除一个节点。这意味着堆出队的总数是n。每个节点可能会被调用一次或多次降低关键字，导致降低关键字的总数最多为m。这给出了运行时间（n T_e + n T_d + m T_k），其中T_k是调用降低关键字所需的时间。

那么这对运行时间有什么影响呢？这取决于您使用的优先队列。以下是一个快速表格，展示了不同优先队列和不同Dijkstra算法实现的总运行时间：

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

从大多数优先队列的类型来看，它们在渐近运行时间上并没有什么区别，并且使用 decrease-key 版本也不太可能有更好的表现。然而，如果您使用 Fibonacci 堆 实现优先队列，那么使用 decrease-key 时 Dijkstra 算法将在渐近意义下更加高效。

简而言之，使用 decrease-key 和一个好的优先队列可以将 Dijkstra 的渐近运行时间降低到比继续进行入队和出队更低的水平。

除此之外，一些更高级的算法，如 Gabow 的最短路径算法，将 Dijkstra 算法作为子程序并且严重依赖于 decrease-key 的实现。它们利用了事先知道有效距离范围的事实，可以基于这个事实构建超级高效的优先队列。

希望这能帮到您！

- templatetypedef

---

+1：我忘记考虑堆了。有一个小问题，由于插入版本的堆每条边都有一个节点，即O(m)，它的访问时间不应该是O(log m)吗？这样总运行时间为O(m log m)。我的意思是，在正常的图中，m不会大于n^2，因此这可以简化为O(m log n)，但在一个图中，两个节点可能通过多个不同权重的边连接，m是无限的（当然，我们可以声称两个节点之间的最小路径仅使用最小的边，并将其减少到正常的图形，但对于nonce而言，这很有趣）。 - rampion

@rampion- 你说得有道理，但我认为通常假定在启动算法之前已经减少了平行边，所以O(log n)与O(log m)不会有太大的影响。通常假定m是O(n^2)。 - templatetypedef

如果我们将（距离，节点）对插入（二叉）堆中，而不是使用 decrease-key，似乎可能导致堆增长到大于节点数 n 的大小。在最坏情况下，我们必须探索所有边缘（边缘数 = m），因此堆将增长到 O(m)，这意味着每个堆插入都是 O(logm)。因此，探索所有边缘的复杂度为 O(mlogm)？！我想象一个非常简单的 DAG，有 n 个节点和 ~n^2=m 条边。在这种情况下，就像 rampion 的情况一样，它会减少到 O(m log n^2) ~ O(m log n)，但我不确定我的先前逻辑是否正确。它正确吗？ - Justin

我刚学到O(logE)等价于O(logV):https://stackoverflow.com/a/65961472/1810877。所以帖子中写的O(m log n)等同于我所想的O(m log m)。但我不确定堆可以增长到大小为m =边数的信念是否正确。这对我意味着复杂度为O(m log m)。 - Justin

如果在探索图时以不同的优先级重新插入节点，则堆大小将为O(m)，您是正确的。 您也是正确的，因为log n <= log m <= 2log n，所以O(log m) = O(log n)。 在写出渐近符号时，惯例是使用log n而不是log m，由于O(m log m) = O(m log n)，因此我们通常使用后者，但O(m log m)仍然是技术上正确的。 - templatetypedef

谢谢@templatetypedef。我正在关注这个优化方案：https://dev59.com/rqDia4cB1Zd3GeqPLvCy#60084732（我在评论中寻求澄清，也欢迎您的输入！）。通过这个小优化，我仍然认为复杂度是~O(m log n)。仍然有相同数量的插入操作，但出队数减少了。前者设定了复杂度的上限；因此，它仍然是O(m log n)。 - Justin

Answer 2

在2007年，有一篇论文研究了使用减少键版本和插入版本之间执行时间的差异。请参见http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf

他们的基本结论是大多数情况下不要使用减少键来处理图形。特别是对于稀疏图形，非减少键比减少键版本快得多。更多细节请参见该论文。

- Marc Meketon

---

http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf‎ 是该论文的有效链接。 - Simd

警告：在链接的论文中存在一个错误。第16页，函数B.2：if k < d[u] 应该改为 if k <= d[u]。 - Xeverous

https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf - qwr

https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf - qwr

Answer 3

有两种方法可以实现Dijkstra算法：一种使用支持减少键的堆，另一种使用不支持减少键的堆。

它们在一般情况下都是有效的，但后者通常更受欢迎。接下来我将使用“m”表示我们图形的边数，“n”表示顶点数：

如果您想要最佳的最坏情况复杂度，您可以选择支持减少键的斐波那契堆：您将获得一个漂亮的O（m + nlogn）。

如果您关心平均情况，您也可以使用二进制堆：您将获得O（m + nlog（m / n）logn）。证明在here，99/100页。如果图形是密集的（m >> n），这两个都倾向于O（m）。

如果您想知道在实际图形上运行它们会发生什么，请查看this论文，正如Mark Meketon在他的答案中建议的那样。

实验结果将显示，在大多数情况下，“简单”的堆会给出最佳结果。

事实上，在使用 decrease-key 的实现中，当使用简单的二叉堆或成对堆时，Dijkstra 的表现要优于使用 Fibonacci 堆。这是因为 Fibonacci 堆涉及更大的常数因子，并且实际 decrease-key 操作的数量往往比最坏情况预测的少得多。

出于类似的原因，一个不需要支持 decrease-key 操作的堆，具有更小的常数因子，实际上表现最佳。特别是当图形稀疏时。

- Nicola Amadio