如何在Dijkstra算法中更新松弛顶点的关键字？

Question

就像在这里所问的那样，我不明白我们如何在堆中找到已松弛顶点的索引。

从编程风格上来看，堆是一个抽象出优先队列细节的黑盒子。现在如果我们需要维护一个哈希表，将顶点键映射到堆数组中相应的索引，那么这需要在堆实现中完成，对吧？

但大多数标准堆不提供执行此映射的哈希表。

解决整个问题的另一种方法是无论如何都将已松弛的顶点添加到堆中。当我们提取最小值时，我们会得到最好的值。为了防止多次提取同一顶点，我们可以将其标记为“已访问”。

因此，我的确切问题是，在行业中处理此问题的典型方式是什么？

与我提到的方法相比，有哪些利弊？

- batman

---

如果有什么不清楚的地方，请问我。我很乐意澄清... - batman

Answer 1

通常情况下，你需要一个特别构造的支持decreaseKey操作的优先队列才能使其运作。我看到过这样的实现方法：如果使用二进制堆，则通过显式地跟踪哈希表的索引来保持优先队列，或者通过具有节点存储在堆中的侵入式优先队列（例如使用二项式堆或斐波那契堆）。有时优先队列的插入操作将返回指向包含新添加键的优先队列中的节点的指针。例如，以下是支持decreaseKey的Fibonacci堆的实现。它的运作方式是使每个插入操作返回指向Fibonacci堆中的节点的指针，这使得在假设您跟踪了返回的指针的情况下可以在O（1）中查找节点。

希望这能帮到你！

- templatetypedef

Answer 2

编程风格上，堆是一个黑箱，它抽象了优先队列的细节。不一定如此。C++和Python都有堆库，提供对数组的函数而非黑箱对象。Go进行了一些抽象，但需要程序员提供类似数组的数据结构以便于其堆操作能够运作。所有这些标准化、行业级别的库中泄漏的抽象都有其原因：某些算法（Dijkstra）需要具有附加操作的堆，否则会降低其他算法的性能。然而，其他算法（堆排序）需要在输入数组上就地执行堆操作。如果您的库的堆给您提供了一个黑箱对象，并且它不足以满足某些算法，则是时候将操作重新实现为数组上的函数，或找到具有所需操作的库了。

- Fred Foo

Answer 3

您提出了一些非常合理的问题，但不幸的是它们有点含糊，所以我们无法给您一个100％确定的“行业标准”答案。但是，我仍然会尝试回答您的问题：

编程风格上，堆是一个黑盒，抽象掉了优先队列的细节。

从技术上讲，优先队列是抽象接口（插入具有优先级的元素，提取优先级最低的元素），而堆是具体实现（基于数组的堆，二项式堆，斐波那契堆等）。

我的意思是使用数组只是实现优先队列的一种特定方式。

如果我们需要维护一个哈希表，将顶点键映射到堆数组中相应的索引，则需要在堆实现中完成，对吗？

是的，因为每次您在数组内移动元素时，都需要更新哈希表中的索引。

但是大多数标准堆不提供执行此映射的哈希表。

是的，这可能非常麻烦。

另一种解决整个问题的方法是将放松的顶点添加到堆中，而不考虑任何其他因素。

我觉得这样做可能可行，但我不认为我曾经看到过有人这样做。在这里使用堆的整个目的是增加性能，通过向堆中添加冗余元素，你会违反这一点。当然，你保留了优先队列的“黑盒特性”，但我不知道这是否值得。此外，额外的pop_heap操作可能会对渐进复杂度产生负面影响，但我必须进行数学计算才能确定。

“在工业界处理这个问题的典型方法是什么？”

首先，问问自己是否可以使用一个愚蠢的数组来代替优先队列。 当然，现在在O（N）而不是O（log n）中找到最小元素，但是实现是最简单的（本身就是一个优势）。此外，如果您的图形密集，使用数组将同样有效，即使您的图形稀疏，根据您的图形大小，它也可能足够高效。

如果确实需要优先队列，则必须找到已实现decreaseKey操作的队列。如果找不到，则我会说自己实现它并不那么糟糕-这可能比尝试找到现有实现并尝试将其与其余代码配合使用更容易。

最后，我不建议使用非常花哨的堆数据结构（例如斐波那契堆）。虽然这些经常出现在教科书中作为获得最优渐近复杂度的一种方式，但实际上它们具有可怕的常数因子，并且与对数相比，这些常数因子是显着的。

- hugomg

Answer 4

这是一个很好的问题，也是那些算法书籍（如CLRS）没有提到的细节之一。

有几种方法可以处理这个问题，包括：

1. 使用支持decreaseKey操作的自定义堆实现
2. 每次“松弛”一个顶点时，您只需将其以新的较低权重添加回堆中，然后编写一种自定义方式以稍后忽略旧元素。您可以利用这样一个事实：只有在权重降低时才会将节点添加到堆/优先队列中。

第一种选项肯定被使用。例如，如果您熟悉OpenSourceRoutingMachine（OSRM），它会在具有数百万节点的图形上搜索以计算道路路由方向。它使用Boost实现的d-ary堆，特别是因为它具有更好的decreaseKey操作，来源。通常也会提到Fibonacci_heap，因为它支持O(1)减少关键操作，但同样地，您可能需要自己编写。

在选项#2中，您最终会进行更多的插入和removeMin操作。如果D是您必须执行的“relax”操作的总数，则您最终会执行D个额外的堆操作。因此，尽管这具有理论上更糟糕的运行时复杂度，在实践中有研究证据表明选项#2可以更高效，因为您可以利用缓存局部性并避免保持指向decreaseKey操作的指针的额外开销（请参见[1]，特别是第16页）。这种方法还具有简单性的优点，并允许您在大多数语言中使用标准库堆/优先队列实现。

为了给您一些关于选项#2的伪代码：

// Imagine this is some lookup table that has the minimum weight
// so far for each node.
weights = {}

while Queue is not empty:
    u = Queue.removeMin()

    // This is our new logic to discard the duplicate entries.
    if u.weight > weights[u]:
        continue

    visit neighbors[u] and relax() each one

作为替代方案，您还可以查看Python标准库 heapq docs，它描述了另一种跟踪堆中“死”条目的方法。它是否有帮助取决于您正在使用的图形表示和顶点距离存储的数据结构。

---

[1] 优先队列和Dijkstra算法2007

- Keyan P