c++ - 将节点引用到优先级队列(迭代器)

Question

我正在尝试使用 priority_queue 实现 Dijkstra 算法(因为我需要跟踪距离源节点最近的节点)。

问题是:当探索一个节点时，它可能会链接到另一个尚未在优先级队列中发现的节点(即链接到优先级队列的元素)。

似乎优先队列不支持迭代器，我如何在发现与其关联的节点时引用优先队列元素？

Answer 1

std::priority_queue<T>既不支持迭代器也不支持降低/增加节点优先级的接口(interface):仅更改元素的优先级不会更新数据结构。您需要的是 std::priority_queue<T> 的基于节点的版本.在 Boost 中有用于该目的的优先级队列.

虽然它不会得到完全正确的复杂性，但您可以使用std::priority_queue<T>对于 Dijkstra 算法:不是存储节点，而是存储从已访问节点到可能未访问节点的边，优先级是使用给定边时目标节点的距离。弹出元素时，您需要检查之前是否访问过该节点。复杂度为 O(m log m)而不是 O(m log n) ，虽然(n 是节点数，m 是边数)。