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

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

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

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

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

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

推荐后者：vector>> 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 在存在负权边时结果不可靠——它依赖“已确定最短距的节点不会再被更新”这一前提，而负权边会破坏该性质。

问小白

免费使用DeepSeek满血版

下载

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

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

#include 
#include 
#include 
#include 

using namespace std;

struct Edge {
    int to, w;
};

vector dijkstra(int n, const vector>& graph, int start) {
    vector dist(n, LLONG_MAX);
    dist[start] = 0;
    // 小顶堆：{距离, 节点}
    priority_queue, vector>, greater>& 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 < dist[v]) {
                dist[v] = new_dist;
                pq.push({new_dist, v});
            }
        }
    }
    return dist;
}

int main() {
    int n = 4, m = 5, s = 0;
    vector> 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 < n; ++i)
        cout << "dist[" << i << "] = " << res[i] << "\n";
}

注意 dist 类型用 long long 防止松弛时溢出；LLONG_MAX 是初始化哨兵值，比较时别用 == 判未访问——应统一用 或 > 比较距离大小。图中节点编号从 0 开始是多数竞赛和库的默认习惯，别在索引上 off-by-one。

立即学习“C++免费学习笔记（深入）”；