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

算法核心思想

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

1. 初始化：起点距离为0，其他所有点距离设为无穷大（通常用一个很大的数表示）。
2. 创建一个优先队列（最小堆），按距离从小到大排序。
3. 从队列中取出距离最小的节点，标记为已访问。
4. 遍历该节点的所有邻居，如果通过当前节点到达邻居的距离更短，则更新邻居的距离。
5. 重复步骤3-4，直到队列为空。

C++代码实现

下面是一个完整的C++实现，使用了标准库中的priority_queue来优化性能。

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;// 定义图的邻接表结构typedef pair<int, int> pii; // {距离, 节点}void dijkstra(int start, vector<vector<pii>>& graph, vector<int>& dist) {    int n = graph.size();    dist.assign(n, INT_MAX); // 初始化所有距离为无穷大    dist[start] = 0;    // 最小堆：{距离, 节点}    priority_queue<pii, vector<pii>, greater<pii>> 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.first;            int weight = edge.second;            // 松弛操作：如果找到更短路径，更新距离            if (dist[u] + weight < dist[v]) {                dist[v] = dist[u] + weight;                pq.push({dist[v], v});            }        }    }}int main() {    int n = 5; // 节点数量    vector<vector<pii>> 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) {        cout << "节点 " << i << ": " << (dist[i] == INT_MAX ? -1 : dist[i]) << "\n";    }    return 0;}  

代码说明

• graph 使用邻接表存储，每个节点保存其邻居和对应的边权。
• dist 数组保存从起点到每个节点的最短距离。
• 使用priority_queue自动维护最小距离节点，提升效率。
• 注意处理“无穷大”情况（用INT_MAX表示），避免整数溢出。

常见应用场景

C++图论编程中，Dijkstra算法广泛应用于：

• 地图导航系统（如高德地图、Google Maps）
• 网络数据包路由
• 游戏AI寻路
• 物流配送路径优化

注意事项

Dijkstra算法不能处理带有负权边的图。如果你的图中存在负权边，请考虑使用Bellman-Ford算法或SPFA算法。

总结

通过本教程，你应该已经掌握了如何在C++中实现Dijkstra算法来解决单源最短路径问题。记住，理解算法的思想比死记代码更重要。多练习、多调试，你就能熟练运用这一强大的C++最短路径算法工具！