C++如何实现Dijkstra算法求解单源最短路径问题

Dijkstra算法的核心思路是从起始节点出发，每次选择当前距离起始节点最近的未访问节点，更新该节点相邻节点的距离，直到所有节点都被访问或者找到目标节点的最短路径。该算法要求图中所有边的权重为非负数，否则无法保证结果的正确性。

Dijkstra算法核心步骤

算法的执行流程可以分为以下几个关键步骤：

• 初始化距离数组，将起始节点的距离设为0，其余节点距离设为无穷大
• 维护一个未访问节点的集合，每次从集合中选取距离最小的节点作为当前节点
• 遍历当前节点的所有邻接节点，计算经过当前节点到达邻接节点的距离，如果小于原有距离则更新
• 将当前节点标记为已访问，从集合中移除，重复上述步骤直到集合为空

基础版C++实现（邻接矩阵存储）

首先使用邻接矩阵存储图结构，实现基础的Dijkstra算法，适合节点数量较少的场景：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 定义无穷大常量
const int INF = INT_MAX / 2;

// Dijkstra算法实现，graph为邻接矩阵，start为起始节点
vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF); // 距离数组，存储每个节点到起始节点的最短距离
    vector<bool> visited(n, false); // 访问标记数组
    dist[start] = 0; // 起始节点距离为0

    for (int i = 0; i < n; i++) {
        // 选取未访问节点中距离最小的节点
        int u = -1;
        int minDist = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        // 如果所有未访问节点距离都是无穷大，说明剩余节点不可达
        if (u == -1) break;
        visited[u] = true;

        // 更新邻接节点的距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist;
}

int main() {
    // 示例图，4个节点，邻接矩阵表示
    // 节点0到1权重2，0到2权重4，1到2权重1，1到3权重5，2到3权重3
    vector<vector<int>> graph = {
        {INF, 2, 4, INF},
        {INF, INF, 1, 5},
        {INF, INF, INF, 3},
        {INF, INF, INF, INF}
    };
    int startNode = 0;
    vector<int> result = dijkstra(graph, startNode);

    cout << "起始节点" << startNode << "到各节点的最短距离：" << endl;
    for (int i = 0; i < result.size(); i++) {
        if (result[i] == INF) {
            cout << "节点" << i << ": 不可达" << endl;
        } else {
            cout << "节点" << i << ": " << result[i] << endl;
        }
    }
    return 0;
}

优化版C++实现（邻接表+优先队列）

基础版本的时间复杂度为O(n²)，当节点数量较多时效率较低，可以使用邻接表存储图，结合优先队列（最小堆）优化节点选取过程，将时间复杂度降低到O(m log n)，其中m是边的数量，n是节点数量：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 定义无穷大常量
const int INF = INT_MAX / 2;
// 定义边的结构体，to是目标节点，weight是边权重
struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

// 定义优先队列中存储的元素，first是距离，second是节点编号
typedef pair<int, int> PII;

// 优化版Dijkstra算法，adj为邻接表，start为起始节点
vector<int> dijkstraOptimized(vector<vector<Edge>>& adj, int start) {
    int n = adj.size();
    vector<int> dist(n, INF);
    dist[start] = 0;
    // 优先队列，默认大顶堆，使用greater改为小顶堆，按距离从小到大排序
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        // 如果当前距离大于记录的距离，说明该节点已经被处理过，跳过
        if (d > dist[u]) continue;

        // 遍历当前节点的所有邻接边
        for (auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    // 示例图，4个节点，邻接表表示
    int n = 4;
    vector<vector<Edge>> adj(n);
    adj[0].push_back(Edge(1, 2));
    adj[0].push_back(Edge(2, 4));
    adj[1].push_back(Edge(2, 1));
    adj[1].push_back(Edge(3, 5));
    adj[2].push_back(Edge(3, 3));

    int startNode = 0;
    vector<int> result = dijkstraOptimized(adj, startNode);

    cout << "起始节点" << startNode << "到各节点的最短距离：" << endl;
    for (int i = 0; i < result.size(); i++) {
        if (result[i] == INF) {
            cout << "节点" << i << ": 不可达" << endl;
        } else {
            cout << "节点" << i << ": " << result[i] << endl;
        }
    }
    return 0;
}

算法注意事项

使用Dijkstra算法时需要注意以下几点：

• 算法仅适用于边权非负的图，如果存在负权边，需要使用Bellman-Ford或者SPFA算法
• 如果图中存在重边，邻接表存储时保留权重最小的边即可，避免不必要的计算
• 优先队列优化版本中，同一个节点可能会被多次加入队列，因此弹出时需要判断当前距离是否大于记录的距离，避免重复处理
• 如果只需要求解到某个特定目标节点的最短路径，可以在弹出目标节点时直接终止算法，提升效率

复杂度分析

两种实现方式的时间复杂度对比如下：

Dijkstra算法C++单源最短路径图论修改时间：2026-07-10 04:54:36