c++ - 在 elogv 时间内实现 dijkstra 算法

Question

1) Create a Min Heap of size V where V is the number of vertices in the given graph. 
   Every node of min heap contains vertex number and distance value of the vertex.
2) Initialize Min Heap with source vertex as root (the distance value assigned to source
   vertex is 0). The distance value assigned to all other vertices is INF (infinite).
3) While Min Heap is not empty, do following
    a) Extract the vertex with minimum distance value node from Min Heap. Let the 
    extracted vertex be u.
    b) For every adjacent vertex v of u, check if v is in Min Heap. If v is in Min Heap
       and distance value is more than weight of u-v plus distance value of u, then 
       update the distance value of v.

我正在考虑用 C++ 为 Dijkstra 实现这个伪代码。这是为了快速实现。我在这里有些困惑，即我们正在使用堆来跟踪未探索区域的相邻顶点的 Dijkstra 分数。在 3b 中我们需要检查 u 的每个相邻顶点 v ，检查 v 是否是 minHeap ， minHeap 是否支持在恒定时间内进行这样的操作，堆是搜索最差的数据结构，搜索它是否存在应该花费线性时间是否在最小堆中，此外，我们必须更新相邻的顶点，因此我们不仅应该知道它是否在最小堆中，而且还要知道它的位置以便我们可以更新它，我们希望所有这些都在 logv 时间内发生，否则有没有快速实现的意义。应该使用什么数据结构来代替堆？

PS:我说的是图作为邻接表实现的实现。

Answer 1

在最坏的情况下，Dijkstra 算法必须执行 |E| DecreaseKey 操作和 |V| ExtractMin 操作。

1. 在二叉堆数据结构中，DecreaseKey 和 ExtractMin 操作的成本都是 O(log(n))。所以算法的总成本是 O(|E|log(|V|) + |V|log(|V|))

2. 如果我们使用斐波那契堆而不是简单的二叉堆，我们可以将总成本降低到 O(|E| + |V|log(|V|)) 因为现在摊销成本DecreaseKey 操作的复杂度是 O(1)

此外，对于图中的每个顶点，您还必须维护指向堆中相应元素的指针数组。这样您就可以在 O(1)

中识别堆中的顶点