【算法】小白也能懂 · 第 15 节：最短路径算法（Dijkstra）

上一节我们学习了并查集，它擅长处理「连通性」问题——判断两个节点是否属于同一个集合。但现实世界中，我们经常遇到另一类问题：从 A 点到 B 点，哪条路最近？这就是今天要讲的最短路径问题，以及解决它的经典算法——Dijkstra（迪杰斯特拉）算法。

1. 什么是最短路径问题

1.1 一个生活中的例子

想象你打开手机地图导航，输入起点和终点。地图 App 会在几秒内告诉你最优路线——这就是最短路径算法在背后工作。

在计算机科学中，最短路径问题可以这样描述：

给定一个带权图（每条边有一个权重，比如距离或时间），找到从某个起点到其他所有节点的最短路径。

1.2 最短路径问题的分类

Dijkstra 算法解决的是单源最短路径问题，且要求所有边的权重为非负数。

2. Dijkstra 算法的核心思想

2.1 贪心策略

Dijkstra 算法的核心思想是贪心：每次从「还没访问过的节点」中，选择距离起点最近的那个，然后用它去更新邻居的距离。

用一个类比来理解：

1. 你在起点，知道到自己的距离是 0
2. 看看所有邻居，更新它们到起点的距离
3. 选出距离最近且还没「确定」的节点，标记为「已确定」
4. 用这个节点去更新它的邻居
5. 重复步骤 3-4，直到所有节点都确定

这就像「涟漪扩散」——从起点出发，一圈一圈向外扩展，每一圈都确定一个最近的节点。

2.2 松弛操作（Relaxation）

Dijkstra 的核心操作叫松弛（Relaxation）。对于一条边 (u, v)，权重为 w：

如果dist[u] + w < dist[v]，就更新dist[v] = dist[u] + w

意思是：如果通过 u 到达 v 比之前的路径更短，就更新 v 的最短距离。

3. 算法步骤详解

我们用一个小图来演示 Dijkstra 的执行过程：

2 A -------> B | | 4 | | 1 | | v v C -------> D 3

起点为 A，求 A 到所有节点的最短距离。

第 1 步：初始化

第 2 步：用 A 更新邻居

A 的邻居是 B（距离 2）和 C（距离 4）。

第 3 步：选出最近的未确定节点 B，标记为已确定

用 B 更新邻居：B 到 D 的距离是 2 + 1 = 3。

第 4 步：选出最近的未确定节点 D，标记为已确定

D 没有未确定的邻居需要更新。

第 5 步：选出 C，全部完成

最终结果：A 到 B 最短距离 2，到 C 最短距离 4，到 D 最短距离 3。

4. 代码实现

4.1 数据结构选择

为了高效地「选出距离最近的未确定节点」，我们使用优先队列（最小堆）。这样每次取最近节点的操作是 O(log N)，而不是遍历所有节点的 O(N)。

图的存储使用邻接表，适合稀疏图。

4.2 C++ 完整代码

#include<iostream>#include<vector>#include<queue>#include<climits>usingnamespacestd;// 边的结构：目标节点 + 权重structEdge{intto,weight;};// Dijkstra 算法vector<int>dijkstra(intn,intstart,vector<vector<Edge>>&graph){vector<int>dist(n,INT_MAX)