c++中如何实现Dijkstra最短路径_c++ Dijkstra最短路径实现方法-C++-PHP中文网

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

冰火之心

发布： 2025-10-13 14:57:01

原创

366人浏览过

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

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

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

1. 数据结构设计

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

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

2. 算法实现步骤

核心流程如下：

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

注意：同一个节点可能多次入队，但只需处理第一次出队的最小距离。

3. 示例代码

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

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

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

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

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

    // 最小堆：(距离, 节点)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> 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<vector<pair<int, int>>> 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<int> 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。

基本上就这些。实现时注意初始化和去重判断，避免重复松弛。

以上就是c++++中如何实现Dijkstra最短路径_c++ Dijkstra最短路径实现方法的详细内容，更多请关注php中文网其它相关文章！