GESP 7级 · 最短路

📖 一句话理解

Dijkstra（迪杰斯特拉）算法求从一个起点到所有其他节点的最短路径。它的核心思想是贪心：每次都选"当前已知距离最小的未确定节点"，用它来更新其他节点的距离。只适用于边权非负的图。

💡 为什么重要？

Dijkstra是最经典的最短路算法，应用极广：地图导航、网络路由、任务调度等。它结合了贪心思想和优先队列，是GESP 7级的核心考点。理解Dijkstra后，学习Bellman-Ford、Floyd等其他最短路算法会容易很多。

📋 前置知识

图的存储：会用邻接表存图
优先队列：priority_queue 的使用（最小堆）
贪心思想：每步选当前最优
pair：用 pair<int,int> 存储 {距离, 节点}

🧠 Dijkstra的核心思想

🔑 算法流程（五步）

初始化：起点距离为0，其他所有节点距离设为无穷大（INF）
选取：从未确定的节点中，选距离最小的那个（贪心！）
确定：该节点的距离已经确定（不会再变小了）
松弛：用这个节点更新它的所有邻居的距离
重复：直到所有节点都确定，或优先队列为空

什么是"松弛"？

💡 松弛（Relaxation）

如果从起点到u的距离是 d[u]，u到v有一条权为w的边，那么从起点到v的距离可能可以更新为 d[u]+w。
如果 d[u]+w < d[v]，就更新 d[v] = d[u]+w。
这个过程就叫"松弛"——用更好的路径"拉紧"v的距离。

🔢 手动推演

5个节点的图：

1→2 权2，1→3 权5
2→3 权1，2→4 权6
3→4 权2，3→5 权8
4→5 权1

从节点1出发：

📊 逐步推演

初始化：d[1]=0, d[2]=INF, d[3]=INF, d[4]=INF, d[5]=INF
选节点1（距离0），松弛邻居：
  d[2] = min(INF, 0+2) = 2
  d[3] = min(INF, 0+5) = 5
选节点2（距离2），松弛邻居：
  d[3] = min(5, 2+1) = 3 ✓ 更新！
  d[4] = min(INF, 2+6) = 8
选节点3（距离3），松弛邻居：
  d[4] = min(8, 3+2) = 5 ✓ 更新！
  d[5] = min(INF, 3+8) = 11
选节点4（距离5），松弛邻居：
  d[5] = min(11, 5+1) = 6 ✓ 更新！
选节点5（距离6），无邻居可更新。
最终：d[1]=0, d[2]=2, d[3]=3, d[4]=5, d[5]=6

💻 完整代码

💻 Dijkstra（优先队列优化，逐行注释）

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

const int N = 105;
const int INF = 1e9;                // 一个很大的数代表"无穷大"
vector<pair<int,int>> adj[N];     // 邻接表：adj[u] = {{v1,w1}, {v2,w2}...}
int n;                              // 节点总数

vector<int> dijkstra(int s) {
    // 第一步：初始化距离数组
    vector<int> d(n + 1, INF);     // 所有距离初始化为无穷大
    d[s] = 0;                       // 起点距离为0

    // 第二步：创建最小堆优先队列
    // pair的第一个元素是距离，第二个是节点编号
    // greater<> 表示按距离从小到大排序（最小堆）
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, s});                // 起点入队，距离0

    // 第三步：主循环
    while (!pq.empty()) {
        auto [dist, u] = pq.top();  // 取出距离最小的节点
        pq.pop();                    // 出队

        // ⚠️ 关键优化：如果这个距离不是最新的，跳过
        // 因为同一个节点可能在队列中有多个不同距离的版本
        if (dist > d[u]) continue;

        // 第四步：松弛u的所有邻居
        for (auto [v, w] : adj[u]) {    // v是邻居，w是边权
            if (d[u] + w < d[v]) {       // 如果通过u到v更近
                d[v] = d[u] + w;         // 更新距离
                pq.push({d[v], v});      // 新距离入队
            }
        }
    }

    return d;   // 返回所有节点到起点的最短距离
}

int main() {
    int m;  // 边数
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});    // 有向边 u→v
        // adj[v].push_back({u, w}); // 如果是无向图，加这行
    }

    vector<int> dist = dijkstra(1);  // 从节点1出发

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF)
            cout << "1到" << i << "不可达" << endl;
        else
            cout << "1到" << i << "最短距离: " << dist[i] << endl;
    }
    return 0;
}

📊 最短路算法对比

📝 各算法适用场景

BFS：无权图最短路，O(V+E)
Dijkstra：非负权图单源最短路，O((V+E) log V)
Bellman-Ford：有负权边的单源最短路，O(VE)
Floyd：所有点对最短路，O(V³)

🚨 易错点

⚠️ 常见错误汇总

Dijkstra不能处理负权边！如果图有负权边，必须用Bellman-Ford。
priority_queue默认是最大堆：要用 greater<> 或自定义比较器才能变成最小堆。
忘记 if (dist > d[u]) continue：这行是关键优化，不是多余的！没有它虽然正确但会变慢。
距离初始化为INF：INF要足够大（比如 1e9），但不能大到溢出（d[u]+w 不能超过INT_MAX）。
多源最短路：Dijkstra是单源的（从一个起点出发）。如果要求所有点对最短路，用Floyd。
pair的比较：priority_queue按pair的第一个元素排序，所以把距离放前面、节点编号放后面。

🎯 练习建议

📝 循序渐进练习路径

先手动推演：在纸上画出Dijkstra的执行过程，理解"松弛"操作。
背模板：Dijkstra的代码模板要熟练到能默写。
做经典题目：
- P4779 【模板】单源最短路径（洛谷Dijkstra模板题）
- P3371 【模板】单源最短路径（可以对比Dijkstra和SPFA）
- P1462 通往奥格瑞玛的道路（Dijkstra + 二分）
对比其他算法：了解Bellman-Ford和Floyd的适用场景。

← 上一个：图的DFS/BFS 📖 返回主目录下一个：并查集 →

最短路 · Dijkstra算法