图论篇 —— 单源最短路

# 图论篇——单源最短路（Dijkstra）

引入

导航软件是怎么算出「从家到学校最快路线」的？把地图看成一张图：每个路口是点，每条路是边，路的长度就是边权。找「从起点到每个点的最短距离」，就是单源最短路问题。最经典、最常考的就是 Dijkstra（迪杰斯特拉）算法。

---

一、基本概念

图：由点（顶点）和连接点的边组成。
边权：边上带的数值，表示经过这条边的代价（距离、时间等）。
单源最短路：给定一个起点，求它到图中所有点的最短距离。
无向图 / 有向图：边是否分方向。

> 例子：一个三角形 A—B—C，AB=5、BC=2、AC=7。从 A 到 C，直接走 AC=7，但先 A→B（5）再 B→C（2）总长 7，两条一样；若 AB=6，则 A→B→C = 8 比直达 AC=7 长，仍走直达。Dijkstra 会帮我们自动比较出最短的那条。

---

二、Dijkstra 核心思路

一句话：每次从未确定的点里，挑「当前距离最小」的点出来，用它去更新它所有邻居的距离，重复直到所有点都确定。

类比：你手上有起点到各点的「暂定距离表」，每次选表里最小的那个点，把它「定下来」（它的最短距离不会再变小了），然后通过这个点看能不能让别的点更近（松弛）。

为什么挑最小的一定正确？

因为边权都 ≥ 0（Dijkstra 的前提），已经定下来的最小距离，不可能再被后面更大的距离绕过而变得更小。所以 Dijkstra 要求边权非负。

---

三、朴素版 Dijkstra 代码

cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int dist[N];        // 起点到各点的最短距离
bool done[N];       // 是否已确定
int a[N][N];        // 邻接矩阵，a[i][j]=i到j的边权
void dijkstra(int s, int n) {
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
        // 找未确定点中距离最小的
        int u = -1, mn = INF;
        for (int j = 1; j <= n; j++)
            if (!done[j] && dist[j] < mn) mn = dist[j], u = j;
        if (u == -1) break;      // 剩下的点都不可达
        done[u] = true;          // 确定 u
        // 用 u 松弛它的邻居
        for (int v = 1; v <= n; v++)
            if (!done[v] && a[u][v] < INF)
                dist[v] = min(dist[v], dist[u] + a[u][v]);
    }
}

复杂度：每次找最小是 O(n)，共 n 次，加松弛 O(n)，总计 O(n²)。

---

四、堆优化版（重点，竞赛常考）

图稀疏时用邻接表 + 优先队列（小根堆），找最小从 O(n) 降到 O(logn)。

cpp
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;      // {距离, 点编号}
const int INF = 0x3f3f3f3f;
const int N = 100005;
vector<PII> g[N];               // g[u] = {(v, w), ...}
int dist[N];
void dijkstra(int s) {
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;   // 过期的记录，跳过
        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

复杂度：O((n + m)logn)，m 为边数，是竞赛最常写的版本。

---

五、局限与变种

不能处理负权边：有负权要用 Bellman-Ford / SPFA（还能判断负环）。
求「每对点」最短：用 Floyd（O(n³)）。
题型常考：最短路 + 建图技巧（拆点、分层图、最短路树）、路径方案数、严格次短路。

---

六、考点与真题提示

代码阅读/完善题常考：dist 数组初始化、松弛条件 dist[v] > dist[u]+w、优先队列里 greater 保证小根堆、if(d>dist[u]) continue 的去重作用。
给一张带权图，问从某点出发到指定点的最短路——先建图再跑堆优化 Dijkstra。
陷阱：无向图要加两条边；INF 要足够大（如 0x3f3f3f3f），避免 INF+w 溢出。

一句话记忆：非负权单源最短路 = 优先队列小根堆，每次取最小点松弛邻居。