c++中如何使用std::priority_queue实现迪杰斯特拉算法_c++技巧【汇总】_技术教程

迪杰斯特拉算法需用最小堆，std::priority_queue默认最大堆，必须显式指定std::greater比较器；pair的first须为距离、second为节点编号以保证字典序正确；需跳过过期条目，即弹出时检查d==dist[u]。

std::priority_queue 默认是最大堆，迪杰斯特拉需要最小堆

直接用 std::priority_queue 声明不加模板参数，默认按 std::less 比较，也就是大根堆 —— 会把距离最大的节点优先弹出，完全违背迪杰斯特拉“每次取当前最近未访问节点”的核心逻辑。

必须显式指定比较器为 std::greater，让它变成小根堆。注意：这要求元素类型支持 operator>，或你提供自定义仿函数/lambda（但 lambda 不能直接用于模板参数，所以通常用 std::greater 或结构体）。

正确写法：

std::priority_queue, std::vector>, std::greater>> pq;

std::pair 的默认 operator> 按字典序比较：先比 first（距离），再比 second（节点编号）。只要 first 是距离，就天然满足最小堆需求
别写成 std::less<...>，那是反的

pair 的 first 必须是距离，second 是节点编号

因为 std::priority_queue 只看 pair 的字典序，而字典序比较时 first 优先级最高。如果把节点放前面、距离放后面，堆会按节点编号排序，完全失效。

✅ 正确：std::make_pair(dist[u], u) —— 距离在前，节点在后
❌ 错误：std::make_pair(u, dist[u]) —— 堆只按 u 排，和距离无关
插入前确保 dist[u] 是当前已知最短距离（松弛后更新）

不能依赖 priority_queue 删除旧状态，必须手动跳过过期条目

std::priority_queue 不支持修改或删除中间元素。当发现更短路径时，你只能把新 (new_dist, v) 入队，但旧的 (old_dist, v) 仍留在堆里。如果不处理，后续可能重复松弛、算错结果、甚至死循环。

标准做法是：每次 pq.top() 取出后，立刻检查 dist[node] == current

_dist。若不等，说明该条目已过期，pop() 后 continue。

示例关键逻辑：

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue;  // 过期条目，跳过
    for (auto &[v, w] : graph[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

这个判断必须放在 pop() 之后、任何处理之前
漏掉它，算法在含重边或多次更新的图上大概率出错

初始化与图表示影响实际写法

没有统一“最佳图结构”，但常见组合会影响代码简洁性：

邻接表推荐用 std::vector<:vector int>>>：外层索引是起点，内层每个 pair
dist 数组必须初始化为一个足够大的数（如 INT_MAX / 2），避免加法溢出；别用 INT_MAX 直接加权值
起点 dist[src] = 0，并立即 pq.push({0, src})
如果图稀疏（边数 m ≈ n），std::priority_queue 版本复杂度是 O((n + m) log m)；稠密图可考虑手写堆或 std::set，但通常没必要