C++最短路径算法详解（从零开始掌握Dijkstra算法实现）

算法前提条件

• 图中所有边的权重必须为非负数（≥0）
• 适用于稀疏图和稠密图（但稠密图效率略低）

C++实现步骤

我们将使用邻接表来表示图，并借助优先队列（最小堆）优化查找过程。

1. 数据结构准备

• vector<vector<pair<int, int>>> graph：邻接表，graph[u] 存储 {v, weight} 表示 u→v 的边
• vector<int> dist：记录起点到每个节点的最短距离
• priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq：最小堆，存储 {distance, node}

2. 完整C++代码实现

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;const int INF = INT_MAX;void dijkstra(int start, const vector<vector<pair<int, int>>>& graph, vector<int>& dist) {    // 初始化距离数组    int n = graph.size();    dist.assign(n, INF);    dist[start] = 0;    // 创建最小堆：{distance, node}    priority_queue<pair<int, int>,                    vector<pair<int, int>>,                    greater<pair<int, int>>> pq;    pq.push({0, start});    while (!pq.empty()) {        int d = pq.top().first;        int u = pq.top().second;        pq.pop();        // 如果当前距离大于已记录的最短距离，跳过        if (d > dist[u]) continue;        // 遍历所有邻居节点        for (const auto& edge : graph[u]) {            int v = edge.first;            int weight = edge.second;            // 松弛操作：如果找到更短路径，更新并加入队列            if (dist[u] + weight < dist[v]) {                dist[v] = dist[u] + weight;                pq.push({dist[v], v});            }        }    }}int main() {    // 示例：构建一个包含5个节点的图（0 ~ 4）    int n = 5;    vector<vector<pair<int, int>>> graph(n);    // 添加边：graph[u].push_back({v, weight})    graph[0].push_back({1, 10});    graph[0].push_back({2, 3});    graph[1].push_back({2, 1});    graph[1].push_back({3, 2});    graph[2].push_back({1, 4});    graph[2].push_back({3, 8});    graph[2].push_back({4, 2});    graph[3].push_back({4, 7});    graph[4].push_back({3, 9});    vector<int> dist;    dijkstra(0, graph, dist);    cout << "从节点0到各节点的最短距离：\n";    for (int i = 0; i < n; ++i) {        if (dist[i] == INF) {            cout << "节点" << i << ": 不可达\n";        } else {            cout << "节点" << i << ": " << dist[i] << "\n";        }    }    return 0;}

3. 代码说明

上述代码实现了标准的Dijkstra算法：

• dijkstra 函数接收起点、图结构和距离数组引用
• 使用 priority_queue 自动按距离从小到大排序
• 通过“松弛”操作不断更新更短路径
• 时间复杂度为 O((V + E) log V)，其中 V 是顶点数，E 是边数

常见应用场景

C++图论编程中的最短路径问题广泛应用于：

• 地图导航（如高德、百度地图路线规划）
• 网络数据包传输路径优化
• 游戏中的NPC寻路（A*算法基于Dijkstra改进）
• 物流配送路径成本最小化

总结

通过本篇最短路径代码教程，你已经掌握了如何用C++实现Dijkstra算法。记住关键点：非负权重、优先队列优化、松弛操作。多加练习，你就能轻松应对各类C++最短路径算法相关问题！

提示：若图中存在负权边，请考虑使用Bellman-Ford或SPFA算法。