c++ - Dijkstra 算法 - 如何使用优先级队列或最小堆？

Question

我一直在努力实现 Dijkstra 算法；更具体地说，是优先队列部分。将顶点添加到数据结构中并使用迭代器遍历所有顶点并找到最小距离；那很容易，但是 n 时间。

我想要的是:

• 能够将顶点插入数据结构
• 提取(返回并移除)距离dist[v]最小的顶点v

我相信要使 Dijkstra 算法正常工作，您应该能够在常数时间内插入顶点并在 log(n) 时间内提取它们；有人建议我可以使用优先级队列和最小堆，但对我来说，保持队列或最小堆有序似乎不太现实，因为距离不断变化。

那么我应该如何声明和使用优先级队列、最小堆或其他数据结构来执行此操作？

Answer 1

您可以使用一对来存储节点和值(第一个元素应该是值，以便优先级队列与该值进行比较)。维护一个 bool 数组 visit [ ]，您将在其中指示您是否访问过某个节点(最初全部为 false)。

每次获取优先级队列的前端元素时，检查您是否访问过此节点，即检查是否 visit[pq.front().second] == false。检查其所有相邻边并添加从此路径到达的节点。如果它是真的那么你应该忽略它，因为你已经用更少的长度访问了它。您不会添加超过 E 条边，因此时间复杂度保持不变。

您可以在此链接中了解有关此方法的更多信息 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#priority .