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

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

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

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

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

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

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

Playground AI

AI图片生成和修图

下载

• 无向图记得双向加边：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";
    }
}