c++中如何实现Dijkstra最短路径_c++ Dijkstra最短路径实现方法

Dijkstra算法用于求解单源最短路径，适用于非负权有向或无向图。使用邻接表存储图，dist数组记录起点到各点的最短距离，优先队列按距离排序，每次取出距离最小节点并松弛其邻边，同一节点可能多次入队但仅首次有效。C++实现中，初始化dist为无穷大，起点距离为0，通过最小堆优化实现O((V+E)logV)时间复杂度，适合稀疏图，需避免重复处理已确定最短距离的节点。

Dijkstra算法用于求解单源最短路径问题，适用于带权有向图或无向图，要求边的权重非负。在C++中，可以通过邻接表 + 优先队列（最小堆）高效实现该算法。

1. 数据结构设计

使用以下结构存储图和距离信息：

• vectorair>>：邻接表，每个节点保存(邻居节点, 边权重)对。
• vector：dist数组，记录从起点到各点的最短距离，初始化为一个大数（如INT_MAX）。
• priority_queue, vector>, greater>>：最小堆，按距离排序，存储(距离, 节点)。

2. 算法实现步骤

核心流程如下：

• 初始化起点距离为0，其余为无穷大，将(0, 起点)加入优先队列。
• 取出当前距离最小的节点u，若已处理过则跳过。
• 遍历u的所有邻接边(u, v)，如果通过u到达v的距离更短，则更新dist[v]并把新距离入队。
• 重复直到队列为空。

3. 示例代码

以下是完整可运行的C++实现：

FaceSwapper

FaceSwapper是一款AI在线换脸工具，可以让用户在照片和视频中无缝交换面孔。

下载

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

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

void dijkstra(vector>>& adj, int start, vector& dist) {
    int n = adj.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;

    // 最小堆：(距离, 节点)
    priority_queue, vector>, greater>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        // 如果当前距离大于已记录的最短距离，跳过
        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n = 5; // 节点数
    vector>> adj(n);

    // 添加边：u -> v，权重w
    adj[0].push_back({1, 10});
    adj[0].push_back({3, 5});
    adj[1].push_back({2, 1});
    adj[1].push_back({3, 2});
    adj[2].push_back({4, 4});
    adj[3].push_back({1, 3});
    adj[3].push_back({2, 9});
    adj[3].push_back({4, 2});
    adj[4].push_back({0, 7});
    adj[4].push_back({2, 6});

    vector dist;
    dijkstra(adj, 0, dist);

    cout << "从节点0出发到各点的最短距离：" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "到节点" << i << "的距离: " << dist[i] << endl;
    }

    return 0;
}

4. 时间复杂度与优化建议

使用优先队列时，时间复杂度为O((V + E) log V)，其中V是节点数，E是边数。

• 适合稀疏图（边较少），邻接表+优先队列是标准做法。
• 若图非常稠密，可用二维数组+朴素Dijkstra（O(V²)）。
• 确保图中无负权边，否则应使用Bellman-Ford或SPFA。