c++中如何实现Dijkstra算法_c++ Dijkstra算法实现方法-C++-PHP中文网

c++中如何实现Dijkstra算法_c++ Dijkstra算法实现方法

冰火之心

发布： 2025-09-28 18:47:12

原创

629人浏览过

Dijkstra算法用于求解单源最短路径问题，适用于非负权有向或无向图。采用邻接表存储图，结合最小堆优化优先队列，从起点开始逐步松弛各节点距离，最终得到到所有节点的最短路径。

c++中如何实现dijkstra算法_c++ dijkstra算法实现方法

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

1. 数据结构选择

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

邻接表：用vector<vector<pair<int, int>>>表示，每个节点保存其邻居及边权。
距离数组：用vector<int>记录起点到各点的最短距离，初始设为无穷大。
优先队列：用priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>实现最小堆，按距离排序。

2. 算法步骤

核心流程如下：

初始化起点距离为0，其余为无穷大，将起点加入优先队列。
取出当前距离最小的未处理节点。
遍历其所有邻接边，尝试通过该节点更新邻居的距离（松弛操作）。
若找到更短路径，则更新距离并将新状态入队。
重复直到队列为空。

3. 完整C++代码示例

以下是一个可运行的Dijkstra实现：

MD5校验和计算小程序（C）

C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。

查看详情

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

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

void dijkstra(vector<vector<pair<int, int>>>& adj, int start) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    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});
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl;
    }
}

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({4, 5});
    adj[1].push_back({2, 1});
    adj[1].push_back({4, 2});
    adj[2].push_back({3, 4});
    adj[3].push_back({0, 7});
    adj[4].push_back({1, 3});
    adj[4].push_back({2, 9});
    adj[4].push_back({3, 2});

    dijkstra(adj, 0);
    return 0;
}

登录后复制