我一直在努力实现 Dijkstra 算法；更具体地说是优先级队列的部分。将顶点添加到数据结构中并使用迭代器遍历所有顶点并找到最小距离；这很容易，但是n次。
我想要的是:
- 能够将顶点插入数据结构
- 提取(返回并删除)具有最小距离dist[v]的顶点v
我相信，要使 Dijkstra 算法正常工作，您应该能够在恒定时间内插入顶点并在 log(n) 时间内提取它们；有人建议我可以使用优先级队列和最小堆，但对我来说，保持队列或最小堆有序似乎不太现实，因为距离不断修改。
那么我应该如何声明和使用优先级队列、最小堆或其他数据结构来执行此操作？
最佳答案
您可以使用一对来存储节点和值(第一个元素应该是该值，以便优先级队列与该值进行比较)。维护一个 bool 数组visit []，您将在其中指示您是否访问过某个节点(最初全部为 false)。
每次获取优先级队列的前面元素时，都会检查是否访问过该节点，即检查是否visit[pq.front().second] == false。检查其所有相邻边并添加从此路径到达的节点。如果这是真的，那么您应该忽略它，因为您已经以较短的长度访问过它。您不会添加超过 E 个边，因此时间复杂度保持不变。
您可以通过此链接 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#priority 了解有关此方法的更多信息。 .
关于c++ - Dijkstra 算法 - 如何使用优先级队列或最小堆？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21933029/