从你家到所有地方的最短路线：Dijkstra算法详解

你有没有用过导航软件？输入起点和终点，导航会立刻告诉你最短的路。如果想知道从你家到整个城市所有地方的最短路线，该怎么办？这时就需要 Dijkstra 算法（读作“迪杰斯特拉”）啦！它是一个专门用来求从一个顶点（起点）到图中所有其他顶点的最短路径的经典算法，但有个前提：所有边的权重（比如距离、花费）必须是正数。比如开车距离、传送时间、游戏里两个关卡之间的经验值消耗，都可以用正整数表示。

生活中为什么需要它？

小明住在地图上的 A 城市，他想知道到其他所有城市的最短开车距离（假设所有道路都是正数距离）。Dijkstra 算法就是帮他找出最短路线的方法。它像一个小秘书：先记下离 A 最近的城市，然后看看通过这个城市能不能让去其他城市的路变短，不断更新。

注意：Dijkstra 不能处理有负数的路（比如有的路是下坡反而省油？不行，只适用于正数）。如果路是负数，算法就会出错，因为贪心思路会失效。

算法核心：贪心 + 松弛

想象你在一个公园里，每个景点（顶点）之间有小路（边），每条小路有长度（权重）。你站在起点，手里拿着一张纸，上面写着“到每个景点的最短距离”，一开始除了起点写 0，其他都写∞（无穷大）。然后你每次从还没确定最短距离的景点里，选一个距离最小的，把它标记为“已确定”，并检查通过它能不能缩短到其他景点的距离。这个过程就像不断往“确定名单”里加人，直到所有景点都确定。

为什么这样能保证正确？ 因为所有边的权重都是正数，所以当前选出的最小距离顶点，不可能被后面更大的距离顶点通过正数距离再缩短。这就是贪心的核心。

算法步骤（手动模拟）

我们以 5 个城市为例，城市编号 0~4，道路如图（有向图，但无向图同理）：

0 到 1 距离 2，0 到 3 距离 6
1 到 0 距离 2，1 到 2 距离 3，1 到 3 距离 8，1 到 4 距离 5
2 到 1 距离 3，2 到 4 距离 7
3 到 0 距离 6，3 到 1 距离 8
4 到 1 距离 5，4 到 2 距离 7

从城市 0 出发，求到所有城市的最短距离。

初始化：dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞, dist[4]=∞。所有顶点未确定。

第1轮：未确定中距离最小的是顶点 0（距离0）。标记 0 为确定。检查 0 的邻居：

到 1：0+2 < ∞，更新 dist[1]=2
到 3：0+6 < ∞，更新 dist[3]=6
当前距离：dist=[0,2,∞,6,∞]

第2轮：未确定中最小的是顶点 1（距离2）。标记 1。检查 1 的邻居：

到 0：已确定，不管
到 2：2+3=5 < ∞，更新 dist[2]=5
到 3：2+8=10 > dist[3]=6，不动
到 4：2+5=7 < ∞，更新 dist[4]=7
当前距离：dist=[0,2,5,6,7]

第3轮：未确定中最小的是顶点 2（距离5）。标记 2。检查 2 的邻居：

到 1：已确定
到 4：5+7=12 > 7，不动
当前距离不变。

第4轮：未确定中最小的是顶点 3（距离6）。标记 3。检查 3 的邻居：

到 0：已确定
到 1：已确定
不动。

第5轮：未确定中只剩顶点 4（距离7）。标记 4。没有邻居需要更新。

最终最短距离：到0:0，到1:2，到2:5，到3:6，到4:7。

完整 C++ 代码：优先队列优化

如果图里有成千上万个顶点，每轮都要扫描所有未确定顶点找最小值，效率太低。所以用优先队列（小根堆） 来快速取出当前距离最小的顶点。堆顶始终是距离最小的顶点，每次弹出 O(log n)，比遍历快很多。

代码中我们使用邻接表存储图，每个元素是一个 pair (邻居顶点, 边的权重)。

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

const int INF = INT_MAX;        // 用 int 最大值表示无穷大
typedef pair<int, int> pii;     // (距离, 顶点编号)，堆里存的

// 从起点 s 出发，计算到所有顶点的最短距离
vector<int> dijkstra(int s, vector<vector<pii>> &graph) {
    int n = graph.size();                        // 顶点个数
    vector<int> dist(n, INF);                    // dist[i]：起点到 i 的最短距离，初始为无穷大
    priority_queue<pii, vector<pii>, greater<pii>> pq; // 小根堆，按距离从小到大排
    dist[s] = 0;                                 // 起点到自己的距离是 0
    pq.push({0, s});                             // 把起点放进堆

    while (!pq.empty()) {
        int d = pq.top().first;   // 当前顶点的已知最短距离
        int u = pq.top().second;  // 当前顶点编号
        pq.pop();

        if (d > dist[u]) continue;  // 如果堆里的距离比已经记录的距离大，说明是过时信息，跳过

        // 遍历顶点 u 的所有邻居
        for (auto &edge : graph[u]) {
            int v = edge.first;   // 邻居顶点
            int w = edge.second;  // 从 u 到 v 的边的权重
            // 松弛操作：如果通过 u 到 v 更短，就更新
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});  // 把更新后的距离和顶点入堆
            }
        }
    }
    return dist;
}

int main() {
    // 5个城市，用邻接表表示有向图（无向图同理，每条边存两次）
    int n = 5;
    vector<vector<pii>> graph(n);

    // 添加边：城市0 -> 城市1，距离2；城市0 -> 城市3，距离6
    graph[0] = {{1, 2}, {3, 6}};
    // 城市1 -> 城市0，距离2；城市1 -> 城市2，距离3；城市1 -> 城市3，距离8；城市1 -> 城市4，距离5
    graph[1] = {{0, 2}, {2, 3}, {3, 8}, {4, 5}};
    // 城市2 -> 城市1，距离3；城市2 -> 城市4，距离7
    graph[2] = {{1, 3}, {4, 7}};
    // 城市3 -> 城市0，距离6；城市3 -> 城市1，距离8
    graph[3] = {{0, 6}, {1, 8}};
    // 城市4 -> 城市1，距离5；城市4 -> 城市2，距离7
    graph[4] = {{1, 5}, {2, 7}};

    int start = 0;  // 从城市0出发
    vector<int> dist = dijkstra(start, graph);
    cout << "从城市" << start << "出发的最短距离:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "到城市" << i << " : " << dist[i] << endl;
    }
    return 0;
}

运行结果：

从城市0出发的最短距离:
到城市0 : 0
到城市1 : 2
到城市2 : 5
到城市3 : 6
到城市4 : 7

代码细节解释

邻接表：graph 是一个向量，每个元素是一个向量，里面存的是 (邻居, 权重)。对于无向图，每条边需要添加两次（比如 graph[0].push_back({1,2}) 和 graph[1].push_back({0,2})）。
优先队列：priority_queue<pii, vector<pii>, greater<pii>> 表示小根堆，堆顶是最小的 pair。注意 pair 的比较器先比较第一个元素（距离），再比较第二个（顶点编号）。
跳过过时信息：弹出堆顶后，如果 d > dist[u]，说明这个 pair 是以前更新的旧值（因为之后可能又用更短距离更新了 dist[u]，但堆里旧的没被删除），直接 continue。这是优化效率的关键。
松弛：if (dist[u] + w < dist[v]) 就是判断能否通过 u 让到 v 的路变短。如果可以，就更新并 push 新 pair。

新手常犯的错误

忘记跳过过时信息：如果不用 if (d > dist[u]) continue;，可能导致同一顶点被多次处理，程序会变慢甚至死循环（因为每次 push 都会增加新 pair）。
堆类型写反：如果写成 priority_queue<pii>（默认大根堆），就会先处理距离大的顶点，算法完全错误。必须用 greater 改成小根堆。
初始化时 INF 设置不合适：如果距离可能超过 INT_MAX-边数*最大边长，相加会溢出。通常用 1e9 或 0x3f3f3f3f 更安全。这里用 INT_MAX，但要注意加法前判断 dist[u] != INF，否则 INF + w 会溢出为负数，导致错误更新。
图是双向路但只加了一条边：如果道路是双向的（无向图），必须在邻接表里同时加入 u->v 和 v->u，否则会漏掉路径。
未考虑起点到不了的点：如果图不连通，有些点的最短距离会保持为 INF，输出时应提示不可达。

为什么不能处理负权边？

假设有一条边权为负，比如从 A 到 B 距离 -5。那么当算法确定 A 为最短后，可能会发现通过 B 能回到 A 且距离更短（A -> B -> A 总共 -3），这就违背了“已确定顶点不会再被更新”的假设。处理负权边需要用 Bellman-Ford 或 SPFA 算法。

还可以怎么扩展？

记录路径：如果想打印具体路线，可以在松弛时记录前驱节点 prev[v] = u，最后从终点回溯。
堆优化 vs 朴素版：当边数远小于顶点数平方时（稀疏图），优先队列版更快；如果是稠密图，可以用数组手动找最小（O(n²)）反而常数小。
其他最短路径算法：学习 Dijkstra 后，可以继续了解 Floyd（多源最短路径，适合小规模图）和 Bellman-Ford（能处理负权边）。

试试修改代码，让它帮你找出从“家”到学校、游乐场、图书馆的最短路线吧！

C++最短路径 Dijkstra 算法