C++实现Dijkstra算法详解（小白也能看懂的最短路径算法教程）

算法核心思想

Dijkstra算法采用贪心策略，每一步都选择当前距离起点最近的未访问节点，并更新其邻居节点的距离。主要步骤如下：

1. 初始化：起点距离为0，其余节点距离设为无穷大（通常用一个大数表示）。
2. 创建一个未访问节点集合。
3. 从集合中选出距离最小的节点，标记为已访问。
4. 更新该节点所有邻居的距离：如果通过当前节点到达邻居的距离更短，则更新邻居的距离值。
5. 重复步骤3-4，直到所有节点都被访问。

C++实现Dijkstra算法

下面是一个使用邻接表和优先队列（最小堆）优化的C++实现。这种实现方式的时间复杂度为 O((V + E) log V)，其中 V 是顶点数，E 是边数。

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;// 定义边结构typedef pair<int, int> Edge; // {权重, 目标节点}void dijkstra(vector<vector<Edge>>& graph, int start, vector<int>& dist) {    int n = graph.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 : graph[u]) {            int v = edge.second;            int weight = edge.first;            // 松弛操作：如果找到更短路径，更新距离            if (dist[u] + weight < dist[v]) {                dist[v] = dist[u] + weight;                pq.push({dist[v], v});            }        }    }}int main() {    int V = 6; // 顶点数量    vector<vector<Edge>> graph(V);    // 添加边：graph[起点].push_back({权重, 终点})    graph[0].push_back({4, 1});    graph[0].push_back({2, 2});    graph[1].push_back({5, 2});    graph[1].push_back({10, 3});    graph[2].push_back({3, 3});    graph[2].push_back({2, 4});    graph[3].push_back({1, 4});    graph[3].push_back({7, 5});    graph[4].push_back({8, 5});    vector<int> dist;    dijkstra(graph, 0, dist);    cout << "从节点0到各节点的最短距离：\n";    for (int i = 0; i < V; ++i) {        if (dist[i] == INT_MAX)            cout << "节点" << i << ": 不可达\n";        else            cout << "节点" << i << ": " << dist[i] << "\n";    }    return 0;}

代码解析

• 邻接表：用 vector<vector<Edge>> 存储图，每个节点保存其出边列表。
• 优先队列：使用 priority_queue 自动取出当前距离最小的节点，提升效率。
• 松弛操作：检查是否可以通过当前节点获得更短路径，是Dijkstra算法的核心。

注意事项

Dijkstra算法不能处理负权边。如果图中存在负权边，请考虑使用Bellman-Ford算法。此外，本实现假设图的节点编号从0开始连续编号。

总结

通过本教程，你已经掌握了如何用C++实现Dijkstra算法。无论是学习C++ Dijkstra算法、理解最短路径算法原理，还是完成课程作业，这个实现都能为你提供坚实基础。希望你能动手尝试修改图的结构，观察输出结果的变化，加深对图论算法实现的理解。

如果你觉得这篇C++图算法教程对你有帮助，不妨多练习几遍，直到完全掌握！