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

上一节我们学习了并查集，它擅长处理「连通性」问题——判断两个节点是否属于同一个集合。但现实世界中，我们经常遇到另一类问题：从 A 点到 B 点，哪条路最近？这就是今天要讲的最短路径问题，以及解决它的经典算法——Dijkstra（迪杰斯特拉）算法。1. 什么是最短路径问题1.1 一个生活中的例子想象你打开手机地图导航，输入起点和终点。地图 App 会在几秒内告诉你最优路线——这就是最短路径算法在背后工作。在计算机科学中，最短路径问题可以这样描述：给定一个带权图（每条边有一个权重，比如距离或时间），找到从某个起点到其他所有节点的最短路径。1.2 最短路径问题的分类类型说明适用算法单源最短路径从一个起点到所有其他点Dijkstra、Bellman-Ford全源最短路径所有点对之间的最短路径Floyd-Warshall无权图最短路径所有边权重相同BFS 即可带权图最短路径边权重不同Dijkstra、Bellman-FordDijkstra 算法解决的是单源最短路径问题，且要求所有边的权重为非负数。2. Dijkstra 算法的核心思想2.1 贪心策略Dijkstra 算法的核心思想是贪心：每次从「还没访问过的节点」中，选择距离起点最近的那个，然后用它去更新邻居的距离。用一个类比来理解：你在起点，知道到自己的距离是 0看看所有邻居，更新它们到起点的距离选出距离最近且还没「确定」的节点，标记为「已确定」用这个节点去更新它的邻居重复步骤 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 步：初始化节点dist已确定？A0✅B∞❌C∞❌D∞❌第 2 步：用 A 更新邻居A 的邻居是 B（距离 2）和 C（距离 4）。节点dist已确定？A0✅B2❌C4❌D∞❌第 3 步：选出最近的未确定节点 B，标记为已确定用 B 更新邻居：B 到 D 的距离是 2 + 1 = 3。节点dist已确定？A0✅B2✅C4❌D3❌第 4 步：选出最近的未确定节点 D，标记为已确定D 没有未确定的邻居需要更新。节点dist已确定？A0✅B2✅C4❌D3✅第 5 步：选出 C，全部完成节点dist已确定？A0✅B2✅C4✅D3✅最终结果：A 到 B 最短距离 2，到 C 最短距离 4，到 D 最短距离 3。4. 代码实现4.1 数据结构选择为了高效地「选出距离最近的未确定节点」，我们使用优先队列（最小堆）。这样每次取最近节点的操作是 O(log N)，而不是遍历所有节点的 O(N)。图的存储使用邻接表，适合稀疏图。4.2 C++ 完整代码#includeiostream#includevector#includequeue#includeclimitsusingnamespacestd;// 边的结构：目标节点 + 权重structEdge{intto,weight;};// Dijkstra 算法vectorintdijkstra(intn,intstart,vectorvectorEdgegraph){vectorintdist(n,INT_MAX)