c++中如何实现Dijkstra算法_c++图论最短路径算法代码【详解】

发布日期： 2026-01-20 阅读量： 作者： 裘德小鎮的故事

因为 std::priority_queue 不支持 decrease-key 操作，旧节点无法更新权值，只能用懒删除：出队时检查 dist[u] 是否匹配，不匹配则跳过。

用 `std::priority_queue` 实现 Dijkstra 时为什么不能直接修改堆中节点的权值

因为 std::priority_queue 不支持动态降键（decrease-key）操作，一旦把一个节点（如 pair 表示 {dist, node}）入队，后续即使更新了该节点的最短距离，旧的入队项仍留在堆里。必须靠「懒删除」绕过这个问题：每次从堆中取出时检查其距离是否已过期。

实际入队的是 {新距离, 节点索引}，不管之前有没有入过
出队后先比对 dist[node] 是否等于当前取出的距离，不等就跳过
否则才进行松弛操作

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

前者更常用、更高效。第一维是起点，第二维每个 pair 是 {终点, 边权}。适合稀疏图，遍历邻居快，内存连续；后者在需要频繁查某条边是否存在（比如带重边检测）时有用，但哈希开销大、缓存不友好。

无向图记得双向加边：graph[u].push_back({v, w}); graph[v].push_back({u, w});
有向图只加一次：graph[u].push_back({v, w});
边权为负？Dijkstra 不适用——换 SPFA 或 Bellman-Ford

初始化 `dist` 数组用 `INT_MAX / 2` 而不是 `INT_MAX`

防止后续做 dist[u] + w 时整数溢出（变成负数），导致错误松弛。取一半是安全上限，足够表示“无穷大”，又留出加法余量。

vector dist(n, INT_MAX / 2);
dist[src] = 0;
最后判断不可达：若 dist[i] == INT_MAX / 2，说明未更新过

#include 
#include 
#include 
#include 
#include 
using namespace std;

int main() {
    int n = 5, m = 6; // 5 nodes, 0-indexed
    vector>> graph(n);
    // add edges: u -> v with weight w
    vector> edges = {{0,1,10}, {0,4,5}, {1,2,1}, {2,3,4}, {3,0,7}, {4,2,3}};
    for (auto [u, v, w] : edges) {
        graph[u].push_back({v, w});
    }

    int src = 0;
    vector dist(n, INT_MAX / 2);
    dist[src] = 0;
    priority_queue, vector>, greater>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue; // lazy deletion
        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << "dist[" << i << "] = ";
        if (dist[i] == INT_MAX / 2) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
}

注意 priority_queue 的比较器写法、dist 初始化边界、以及每次出队后必须校验是否过期——这三点漏掉任意一个，算法就可能算错或死循环。

上一篇: iPhone 15 Pro Max拍照总是偏暗怎么办

下一篇: 荣耀X50连接WiFi频繁断开怎么办荣耀X50网络稳定性优

c++中如何实现Dijkstra算法_c++图论最短路径算法代码【详解】

随便看看

南昌壹佳企网络通信有限公司