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 是 {终点, 边权}。适合稀疏图，遍历邻居快，内存连续；后者在需要频繁查某条边是否存在（比如带重边检测）时有用，但哈希开销大、缓存不友好。

• 无向图记得双向加边：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 << "INFn";         else cout << dist[i] << "n";     } }

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