如何更新Dijkstra算法中松弛顶点的密钥？

Question

就像有人问here， 我不明白，我们怎么能找到在堆轻松顶点的索引。

编程风格明智的，heap是一个黑箱抽象掉优先级队列的细节。现在，如果我们需要维护一个将顶点键映射到堆数组中相应索引的散列表，那需要在heap实现中完成，对吧？

但是大多数标准堆并不提供这样的映射的散列表。

另一种方式来处理这个问题，全是轻松的顶点添加到堆不顾一切。当我们提取最小值时，我们会得到最好的一个。为了防止多次提取同一个顶点，我们可以标记它访问了。

所以我确切的问题是，典型的（在业内）处理这个问题的方式是什么？

比较我提到的方法有哪些优缺点？

Answer 1

你问一些非常有效的问题，但不幸的是他们都是那种模糊的，所以我们不能给你一个100％固体“行业标准”的答案。不过，我会尽力去超过你的观点呢：

编程风格明智的，堆是一个黑箱抽象掉优先级队列的细节

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

我想说的是，使用数组只是实现优先级队列的一种特殊方式。

现在，如果我们需要维护一个散列表，它将顶点键映射到堆数组中的相应索引，那么这需要在堆实现中完成，对吧？

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

但是大多数标准堆并不提供这样的映射的散列表。

是。这可能非常烦人。

解决这个问题的另一种方法是无论任何事情，都可以将放松的顶点添加到堆中。

我想这可以工作，但我不认为我见过任何人这样做。在这里使用堆的关键是要提高性能，并在堆中添加多余的元素，这是违背它的。当然，你保留优先队列的“黑盒子”，但我不知道这是否值得。另外，额外的pop_heap操作可能会对你的渐近复杂性产生负面影响，但我不得不做数学检查。

处理这个问题的典型方法是什么？

首先，问问自己是否可以使用哑数组而不是优先级队列。 当然，现在找到O（N）中的最小元素而不是O（log n），但实现是最简单的（本身就是一个优点）。此外，如果图形密集，并且即使图形稀疏，使用数组效果也会一样高，这取决于图形的大小。

如果你确实需要一个优先级队列，那么你将不得不找到一个执行了reduceKey操作的队列。如果你找不到它，我会说它自己实现它并不坏 - 它可能比试图找到一个现有的实现然后试图使其与其他代码相适应更麻烦。

最后，我会不是建议使用真正的花式堆数据结构（如斐波那契堆）。虽然这些经常出现在教科书中作为获得最佳渐近线的方法，但实际上它们具有可怕的常数因子，与对数相比，这些常数因子是显着的。

Answer 2

编程风格上，堆是一个黑盒子，它抽象出优先级队列的细节。

不一定。 C++和Python都有堆库，它们在数组上提供函数而不是黑箱对象。 Go抽象了一点，但要求程序员为其堆操作提供一个类似数组的数据结构。

所有这些抽象的标准化，产业实力库泄漏是有原因的：一些算法（Dijkstra算法）需要额外的操作，这会降低其他算法的性能堆。然而其他算法（堆排序）需要在输入阵列上就地工作的堆操作。如果你的图书馆的堆给你一个黑盒子对象，并且它不能满足某些算法，那么是时候重新实现操作作为数组的函数，或者找到一个具有你需要的操作的库。

Answer 3

通常情况下，你需要的是支持，为了得到这个工作的decreaseKey操作的特殊构造的优先级队列。我已经看到这通过让优先级队列明确跟踪索引的哈希表（如果使用二进制堆）或通过具有入侵优先级队列（其中存储的元素是堆中的节点）来实现的（如果使用二项堆或Fibonacci堆，例如）。有时，优先级队列的插入操作会返回一个指向保存新添加的密钥的优先级队列中的节点的指针。作为一个例子，这里是一个支持decreaseKey的implementation of a Fibonacci heap。它通过让每个插入操作返回一个指向Fibonacci堆中节点的指针来工作，这使得可以在O（1）中查找节点，假设您跟踪返回的指针。

希望这会有所帮助！