c++中如何实现迪杰斯特拉算法_c++ Dijkstra最短路径算法详解-C++-PHP中文网

std::priority_queue不支持堆内元素修改，更新距离后需push新节点并跳过过时条目；邻接表推荐vector；Dijkstra不适用于负权边，应改用Bellman-Ford或SPFA。

c++中如何实现迪杰斯特拉算法_c++ dijkstra最短路径算法详解

用 `std::priority_queue` 实现 Dijkstra 时为什么距离更新后队列不自动排序

因为 std::priority_queue 不支持堆内元素修改，插入后无法调整位置。常见错误是：发现更短距离时直接 push 新节点，却不标记旧节点失效——导致后续重复处理过时的高代价路径。

必须配合一个 dist[] 数组实时记录当前已知最短距离
每次从堆中 pop 出节点时，先检查 dist[u] != 当前弹出的距离，若不等说明已过时，直接跳过
不要尝试用 make_heap 手动重排队列——开销大且易错

邻接表建图该用 `vector>` 还是 `vector>>`

推荐后者：vector>&gt graph(n)，其中 graph[u] 存储所有从 u 出发的边，pair 表示 {v, weight}（终点与权重）。

前者（单个 vector）只能表达全局边集，无法快速枚举某点的邻接点，Dijkstra 中每轮需遍历所有边，时间退化为 O(EV)
后者支持 O(degree(u)) 遍历邻居，总复杂度保持 O((V + E) log V)
若图稀疏（E ≈ V），空间也更紧凑；稠密图可考虑邻接矩阵，但仅限 V

遇到负权边就崩？不是说 Dijkstra 不能处理负权吗

是的，标准 Dijkstra 在存在负权边时结果不可靠——它依赖“已确定最短距的节点不会再被更新”这一前提，而负权边会破坏该性质。

Upstream Recon

在与开源项目（如提交PR、Issue或评论）互动前，先对其进行调研。适用于：提交Issue、提交PR或发表评论之前。

下载

若你发现算法输出路径比实际长，或 dist[v] 在后期又被更小值覆盖，大概率是输入含负权边
此时应换用 Bellman-Ford（支持负权、可检测负环）或 SPFA（Bellman-Ford 的队列优化版）
注意：负权环存在时，最短路无定义；Dijkstra 对此完全无感知，也不会报错，只会静默给出错误结果

C++ 完整可运行的 Dijkstra 实现（带注释）

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int to, w;
};

vector<long long> dijkstra(int n, const vector<vector>>& graph, int start) {
    vector<long long> dist(n, LLONG_MAX);
    dist[start] = 0;
    // 小顶堆：{距离, 节点}
    priority_queue<pair long int>, vector<pair long int>>, greater<pair long int>>& pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue; // 过时条目，跳过
        for (auto& e : graph[u]) {
            int v = e.to;
            long long new_dist = dist[u] + e.w;
            if (new_dist &gt graph(n);
    // 添加边：u->v 权重 w
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 6});
    graph[2].push_back({3, 3});

    auto res = dijkstra(n, graph, s);
    for (int i = 0; i <p>注意 <code>dist</code> 类型用 <code>long long</code> 防止松弛时溢出；<code>LLONG_MAX</code> 是初始化哨兵值，比较时别用 <code>==</code> 判未访问——应统一用 <code> 或 <code>></code> 比较距离大小。图中节点编号从 <code>0</code> 开始是多数竞赛和库的默认习惯，别在索引上 off-by-one。</code></p></pair></pair></pair></long></vector></long></climits></queue></vector></iostream>