c++ - c++ std::priority_queue 是 dijkstra 队列的正确结构吗

Question

我不认为 c++ 优先级队列是 dijkstra 队列的正确结构，因为它不包含用于轻松查找或删除元素的功能。

正确的结构是斐波那契堆，但 std 库中没有。

有人对更好的 C++ 实现结构有建议吗？

Answer 1

您可以在其中使用std::set和存储一对<distance, vertex>。要查找和删除元素，您可以与数组中的每个顶点保持距离，或者std::vector快速获取给定顶点的 pair<distance, vertex>。最近的未访问顶点总是在集合的第一个元素中（并且可以使用 获得set.begin()）。

Answer 2

对于大多数实际目的，std::priority_queue基于实现对于稀疏图来说已经足够好了。以这种方式实现 Dijkstra 的运行时间为O(E log V). 如果您有足够密集的图，您可以简单地使用O(V*V)Dijkstra 算法的基本版本。随着图变得越来越密集，Fib-heap 版本的渐近线更接近于 vanilla 实现。