Dijkstra 最短路

前言：导航软件是怎么找最短路的？

打开手机导航，输入起点和终点，几秒钟就能给出最短路线。它是怎么做到的？

如果每条路的长度都一样（比如都是 1 公里），那 BFS 就够了——先扩展 1 公里能到的，再扩展 2 公里能到的……但现实中每条路的长度不同。一条 100 公里的高速公路和一条 5 公里的小路，不能同等对待。

Dijkstra 算法是 BFS 的自然推广。核心想法一样：从起点出发，由近及远地探索。但因为边权不同，不能用普通队列（先进先出），而要用优先队列——每次取出”当前已知距离最小”的点。

一个关键的性质：当某个点从优先队列中被取出时，它的最短距离就已经确定了，不可能通过其他路径更短。为什么？因为队列里所有其他点的距离都不比它小，而边权是非负的，通过它们绕路不可能更短。

这就是 Dijkstra 的贪心选择——也是它不能处理负权边的原因。如果有负权边，“通过更远的点绕回来”可能反而更短，贪心就不成立了。

这篇笔记会从贪心策略出发，给出堆优化的 C++ 实现，然后通过一道城市间最短路的例题巩固。

Dijkstra 最短路

问题的本质

给定带权有向图（边权非负）和起点 $s$，求 $s$ 到所有其他顶点的最短距离。

朴素做法：每次扫描所有未确定顶点找最小距离，$O(V^2)$。稠密图还行，稀疏图（边数 $E \ll V^2$）浪费严重。

关键洞察：只需要高效地取出”当前距离最小的未确定顶点”——优先队列（小根堆）天然支持这个操作。

贪心策略

Dijkstra 的核心是一个贪心选择：

每次从所有未确定的顶点中，取出距离 $s$ 最近的那个。由于边权非负，这个顶点的最短距离已经确定了，不可能通过其他路径更短。

为什么对？因为任何其他路径到达这个顶点，中间必然经过更远的顶点（它已经是最近的了），加上非负的边权，不可能更短。

堆优化实现

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

typedef pair<long long, int> pli;  // (距离, 顶点)
const long long INF = 1e18;

vector<pli> adj[MAXN];  // adj[u] = {(w, v)}：u 到 v，边权 w
long long dist[MAXN];

void dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;

    priority_queue<pli, vector<pli>, greater<pli>> pq;  // 小根堆
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 过期的条目，跳过
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

if (d > dist[u]) continue 是关键——堆里可能有同一个顶点的多个条目（距离不同），只有最小的那个会生效，其余的是”过期条目”直接跳过。这比手动 decrease-key 简洁得多。

复杂度

版本	时间	适用
朴素	$O(V^2)$	稠密图
堆优化	$O((V+E) \log V)$	稀疏图

局限性

不能处理负权边。如果有负权边，“当前最近的顶点已确定”这个贪心性质就不成立了——可能通过负权边绕回来更短。负权边需要 Bellman-Ford（$O(VE)$）或 SPFA。

例题：单源最短路

$n$ 个城市、$m$ 条双向道路，每条路有长度。求从城市 1 到城市 $n$ 的最短路长度。

$1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

typedef pair<long long, int> pli;
const int MAXN = 100006;
const long long INF = 1e18;

vector<pli> adj[MAXN];
long long dist[MAXN];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});  // 双向
    }

    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;

    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[n] == INF) printf("-1\n");
    else printf("%lld\n", dist[n]);
    return 0;
}

解析：$n = 10^5$ 级别，朴素 $O(n^2)$ 不可行，堆优化 $O((n+m) \log n)$ 轻松通过。图的存储用邻接表（vector），空间 $O(n+m)$。注意 dist 初始化为 INF，终点不可达时输出 -1。