一文搞懂 Dijkstra 最短路径算法
一文搞懂 Dijkstra 最短路径算法：原理、实现与应用
在计算机科学和图论领域，寻找图中两点之间的最短路径是一个经典且至关重要的问题。无论是规划城市间的行车路线、优化网络数据包的传输路径，还是在复杂系统中寻找最高效的资源分配方式，最短路径算法都扮演着核心角色。而在众多解决此类问题的算法中，Dijkstra（迪杰斯特拉）算法无疑是最著名和应用最广泛的算法之一。
本文将深入浅出地探讨 Dijkstra 算法，从基本概念、核心思想、执行步骤，到具体实现、复杂度分析、局限性以及实际应用，力求让你通过这一篇文章，全面掌握 Dijkstra 算法的精髓。
一、最短路径问题概述
在介绍 Dijkstra 算法之前，我们首先需要明确什么是“最短路径问题”。
在一个带权图 (Weighted Graph) 中，每条边都被赋予了一个数值，称为权重 (Weight) 或成本 (Cost)。这个权重可以代表距离、时间、费用或其他任何衡量“阻力”或“消耗”的指标。
最短路径问题就是要在一个带权图中，找到从一个指定的源节点 (Source Node) 到图中其他所有节点（或某个特定目标节点 (Destination Node)）的路径中，使得路径上所有边的权重之和最小的那条路径。
根据问题的具体需求，最短路径问题可以细分为：
- 单源最短路径 (Single-Source Shortest Path - SSSP)：找到从一个固定源节点到图中所有其他节点的最短路径。Dijkstra 算法主要解决的就是这类问题（在非负权重的条件下）。
- 单目的地最短路径 (Single-Destination Shortest Path)：找到从图中所有节点到某个固定目标节点的最短路径。可以通过将图中所有边的方向反转，然后从目标节点运行单源最短路径算法来解决。
- 单对最短路径 (Single-Pair Shortest Path)：找到图中指定的一对节点（源节点和目标节点）之间的最短路径。通常可以通过运行单源最短路径算法，并在找到目标节点的最短路径后停止（如果算法允许）或运行完成来解决。
- 所有节点对最短路径 (All-Pairs Shortest Path - APSP)：找到图中每一对节点之间的最短路径。可以通过对每个节点运行一次单源最短路径算法（如 Dijkstra 或 Bellman-Ford），或者使用专门的 APSP 算法（如 Floyd-Warshall）来解决。
Dijkstra 算法是解决非负权重图下单源最短路径问题的经典贪心算法。
二、Dijkstra 算法的核心思想
Dijkstra 算法由荷兰计算机科学家艾兹赫尔·W·迪杰斯特拉 (Edsger W. Dijkstra) 于 1956 年提出。其核心思想是贪心策略 (Greedy Strategy) 和逐步扩展 (Iterative Expansion)。
算法维护两个集合：
- 已确定最短路径的节点集合 (S)：初始时只包含源节点。集合 S 中的节点，其从源节点出发的最短路径长度已经确定，不会再改变。
- 未确定最短路径的节点集合 (U)：初始时包含除源节点外的所有其他节点。
算法还维护一个距离数组 dist[]，dist[v] 存储当前已知的从源节点 s 到节点 v 的最短路径长度的估计值。初始时，dist[s] = 0，对于所有其他节点 v，dist[v] = ∞ (表示尚未找到路径或路径无限长)。
算法的执行过程可以概括为：
- 初始化：将源节点
s加入集合 S，dist[s]设为 0，其他所有节点的dist值设为无穷大。 -
迭代：重复以下步骤，直到所有节点都被加入集合 S（或者说集合 U 为空）：
- 选择节点：从集合 U 中，选择一个
dist值最小的节点u。这个选择是贪心的，因为它总是选择当前看起来“最近”的节点。Dijkstra 证明了这个选择在非负权重下是正确的，即此时dist[u]就是源节点到u的真正最短路径长度。 - 移入集合 S：将选出的节点
u从集合 U 移到集合 S。 - 松弛操作 (Relaxation)：对于刚刚移入集合 S 的节点
u的所有邻居节点v（且v仍在集合 U 中），进行“松弛”操作。检查通过节点u到达节点v是否能获得更短的路径。即，比较dist[v]（当前已知的到v的最短距离）和dist[u] + weight(u, v)（通过u到达v的路径长度）。如果后者更小，则更新dist[v]的值为dist[u] + weight(u, v)。这一步是关键，它不断优化从源点到各节点的路径估计值。
- 选择节点：从集合 U 中，选择一个
-
结束：当所有节点都被访问过（即集合 U 为空），算法结束。此时，
dist数组中存储的就是从源节点到所有其他节点的最短路径长度。
为什么贪心选择是正确的？
这是 Dijkstra 算法的精髓所在，其正确性依赖于边的权重不能为负。
假设算法在某一步从 U 中选择了 dist 值最小的节点 u。这意味着当前所有已知路径中，到 u 的这条路径是最短的。是否存在另一条尚未发现的、通过 U 中其他节点 w 到达 u 的更短路径呢？
假设存在这样一条更短路径 s -> ... -> w -> ... -> u。由于边的权重非负，这条路径上的任何中间节点（包括 w）的 dist 值必然小于或等于最终到达 u 的路径长度。因为这条路径比当前找到的 s -> ... -> u 路径更短，所以 dist[w]（或路径上某个 w 之前的节点）必然小于 dist[u]。但这与我们选择 u 作为 U 中 dist 值最小的节点的假设相矛盾。因此，当边的权重非负时，每次贪心选择的节点的 dist 值就是其最终的最短路径长度。
如果存在负权重边，这个证明就不成立了。一条包含负权重边的路径可能会使得一个当前 dist 值较大的节点，在未来通过这条负边路径变成更优的选择，从而推翻了之前的贪心选择。
三、Dijkstra 算法的详细步骤与示例
为了更清晰地理解算法流程，我们通过一个具体的例子来逐步演示。
示例图：
假设我们有以下带权无向图，我们要计算从节点 A 出发到所有其他节点的最短路径。
(1) B ----(3)---- D
/ | / \ | (1)
(6)/ | (2) / \ (5) E
/ | / (1) \ / | (5)
A --(3)--> C-------(2)---- F
节点：A, B, C, D, E, F
边和权重：(A, B, 6), (A, C, 3), (B, C, 2), (B, D, 1), (C, D, 1), (C, E, 5), (D, E, 3), (E, F, 2), (D, F, 1) (假设这是一个无向图，权重相同；如果是单向按箭头)
算法步骤：
-
初始化：
- 集合 S = {}
- 集合 U = {A, B, C, D, E, F}
dist数组：dist[A]=0,dist[B]=∞,dist[C]=∞,dist[D]=∞,dist[E]=∞,dist[F]=∞prev数组（用于记录路径）：prev[A]=null,prev[B]=null, ... ,prev[F]=null(可选，但用于路径重建)
-
迭代 1：
- 选择节点：U 中
dist最小的节点是 A (dist[A]=0)。 - 移入 S：S = {A}, U = {B, C, D, E, F}
- 松弛邻居 (A 的邻居是 B 和 C)：
- 对于 B：
dist[A] + weight(A, B) = 0 + 6 = 6。因为6 < dist[B](∞)，更新dist[B] = 6,prev[B] = A。 - 对于 C：
dist[A] + weight(A, C) = 0 + 3 = 3。因为3 < dist[C](∞)，更新dist[C] = 3,prev[C] = A。
- 对于 B：
- 当前状态：
dist = {A:0, B:6, C:3, D:∞, E:∞, F:∞}
- 选择节点：U 中
-
迭代 2：
- 选择节点：U 中
dist最小的节点是 C (dist[C]=3)。 - 移入 S：S = {A, C}, U = {B, D, E, F}
- 松弛邻居 (C 的邻居是 A, B, D, E)：
- A 在 S 中，忽略。
- 对于 B：
dist[C] + weight(C, B) = 3 + 2 = 5。因为5 < dist[B](6)，更新dist[B] = 5,prev[B] = C。 (注意：路径 A->B 被 A->C->B 替代) - 对于 D：
dist[C] + weight(C, D) = 3 + 1 = 4。因为4 < dist[D](∞)，更新dist[D] = 4,prev[D] = C。 - 对于 E：
dist[C] + weight(C, E) = 3 + 5 = 8。因为8 < dist[E](∞)，更新dist[E] = 8,prev[E] = C。
- 当前状态：
dist = {A:0, B:5, C:3, D:4, E:8, F:∞}
- 选择节点：U 中
-
迭代 3：
- 选择节点：U 中
dist最小的节点是 D (dist[D]=4)。 - 移入 S：S = {A, C, D}, U = {B, E, F}
- 松弛邻居 (D 的邻居是 B, C, E, F)：
- C 在 S 中，忽略。
- 对于 B：
dist[D] + weight(D, B) = 4 + 1 = 5。因为5不小于dist[B](5)，不更新。 - 对于 E：
dist[D] + weight(D, E) = 4 + 3 = 7。因为7 < dist[E](8)，更新dist[E] = 7,prev[E] = D。 (路径 A->C->E 被 A->C->D->E 替代) - 对于 F：
dist[D] + weight(D, F) = 4 + 1 = 5。因为5 < dist[F](∞)，更新dist[F] = 5,prev[F] = D。
- 当前状态：
dist = {A:0, B:5, C:3, D:4, E:7, F:5}
- 选择节点：U 中
-
迭代 4：
- 选择节点：U 中
dist最小的节点是 B (dist[B]=5)。（注意：此时 F 的dist也是 5，选择哪个取决于实现，通常选择先遇到的或按节点编号排序。这里假设选择 B）。 - 移入 S：S = {A, C, D, B}, U = {E, F}
- 松弛邻居 (B 的邻居是 A, C, D)：
- A, C, D 都在 S 中，全部忽略。
- 当前状态：
dist = {A:0, B:5, C:3, D:4, E:7, F:5}(无变化)
- 选择节点：U 中
-
迭代 5：
- 选择节点：U 中
dist最小的节点是 F (dist[F]=5)。 - 移入 S：S = {A, C, D, B, F}, U = {E}
- 松弛邻居 (F 的邻居是 D, E)：
- D 在 S 中，忽略。
- 对于 E：
dist[F] + weight(F, E) = 5 + 2 = 7。因为7不小于dist[E](7)，不更新。
- 当前状态：
dist = {A:0, B:5, C:3, D:4, E:7, F:5}(无变化)
- 选择节点：U 中
-
迭代 6：
- 选择节点：U 中
dist最小的节点是 E (dist[E]=7)。 - 移入 S：S = {A, C, D, B, F, E}, U = {}
- 松弛邻居 (E 的邻居是 C, D, F)：
- C, D, F 都在 S 中，全部忽略。
- 当前状态：
dist = {A:0, B:5, C:3, D:4, E:7, F:5}(无变化)
- 选择节点：U 中
-
结束：集合 U 为空，算法结束。
最终结果：
* dist = {A:0, B:5, C:3, D:4, E:7, F:5}
* prev 数组（反向追溯可得路径）：
* prev[B]=C (路径 B<-C<-A => A->C->B)
* prev[C]=A (路径 C<-A => A->C)
* prev[D]=C (路径 D<-C<-A => A->C->D)
* prev[E]=D (路径 E<-D<-C<-A => A->C->D->E)
* prev[F]=D (路径 F<-D<-C<-A => A->C->D->F)
路径重建：
要找到从 A 到 F 的最短路径，可以从 F 开始，通过 prev 数组回溯：
F -> prev[F]=D -> prev[D]=C -> prev[C]=A。
反转得到路径：A -> C -> D -> F，总长度为 dist[F] = 5。
四、Dijkstra 算法的实现
实现 Dijkstra 算法通常需要以下数据结构：
-
图的表示：
- 邻接矩阵 (Adjacency Matrix)：用 V x V 的二维数组
graph[i][j]存储边(i, j)的权重。优点是查询边权重快 (O(1))，缺点是空间复杂度高 (O(V^2))，不适合稀疏图。 - 邻接表 (Adjacency List)：用数组（或哈希表）存储每个节点，每个节点关联一个链表（或动态数组），链表中存储其所有邻居节点及对应的边权重。优点是空间复杂度低 (O(V+E))，适合稀疏图。Dijkstra 算法通常在稀疏图上表现更好，因此邻接表更常用。
- 邻接矩阵 (Adjacency Matrix)：用 V x V 的二维数组
-
距离数组
dist[]：大小为 V 的一维数组，存储源点到各点的当前最短距离估计值。 -
标记数组
visited[]或集合 S：用于记录哪些节点已经确定了最短路径（即已加入集合 S）。可以用布尔数组或集合实现。 -
优先队列 (Priority Queue)（优化实现的关键）：用于高效地找到集合 U 中
dist值最小的节点。
实现方式：
1. 朴素实现 (使用数组查找最小值)
- 数据结构：邻接矩阵或邻接表，
dist[]数组，visited[]布尔数组。 -
流程：
- 初始化
dist和visited。 - 循环 V 次：
- 在所有未访问 (
visited[i] == false) 的节点中，线性扫描dist数组，找到dist值最小的节点u(O(V) 操作)。 - 标记
u为已访问 (visited[u] = true)。 - 遍历
u的所有邻居v：- 如果
v未访问且dist[u] + weight(u, v) < dist[v]，则更新dist[v]（松弛操作）。
- 如果
- 在所有未访问 (
- 初始化
-
时间复杂度：
- 每次循环需要 O(V) 时间找到最小
dist值的节点。共循环 V 次，这部分是 O(V^2)。 - 松弛操作总共会对每条边检查一次（对于邻接表）或 V^2 次（对于邻接矩阵）。使用邻接表时，松弛的总时间是 O(E)。
- 因此，朴素实现的总时间复杂度是 O(V^2) (在使用邻接矩阵或邻接表，但用线性扫描找最小值时)。对于稠密图 (E 接近 V^2)，这可以接受，但对于稀疏图 (E 接近 V)，效率不高。
- 每次循环需要 O(V) 时间找到最小
2. 优化实现 (使用优先队列)
- 数据结构：邻接表，
dist[]数组，优先队列。不需要显式的visited数组，因为节点一旦从优先队列中取出，就相当于加入了集合 S。 - 优先队列：存储
(distance, node)对，并根据distance进行排序（最小堆）。这样可以快速 (O(log V)) 找到 U 中dist值最小的节点。 -
流程：
- 初始化
dist数组 (源点为 0，其余为无穷大)。 - 创建一个空的最小优先队列
pq。 - 将源节点
(0, s)加入pq。 - 当
pq不为空时：- 从
pq中提取（删除）具有最小distance的节点(d, u)(O(log V) 操作)。 - 检查冗余：如果
d > dist[u]，说明这个(d, u)是之前插入的旧信息（因为u可能已经被更短的路径更新过并重新入队），直接跳过本次循环，处理下一个pq中的元素。 - 标记访问（隐式）：当一个节点
u以其当前的最终最短距离dist[u]第一次从优先队列中取出时，它就相当于被加入了集合 S。 - 松弛邻居：遍历
u的所有邻居v：- 计算新路径距离
new_dist = dist[u] + weight(u, v)。 - 如果
new_dist < dist[v]：- 更新
dist[v] = new_dist。 - 将
(new_dist, v)加入pq(O(log V) 操作)。注意：这里是插入，不是更新优先队列中已有的v(虽然某些优先队列实现支持decrease-key操作，但直接插入通常更简单且复杂度相似)。旧的、距离更大的v条目会在之后被取出时因检查冗余而被忽略。
- 更新
- 计算新路径距离
- 从
- 初始化
-
时间复杂度：
- 初始化：O(V)
- 优先队列操作：
- 每个节点最多入队一次（当其
dist值被改善时）。最坏情况下，每条边(u, v)都可能导致一次v的入队操作（如果v的dist值不断被优化）。总的入队次数最多是 O(E)。 - 每次入队操作（插入）是 O(log V)。
- 每个节点最终会以其最短路径距离从优先队列中被提取出来一次。总共有 V 次提取操作。
- 每次提取操作（删除最小）是 O(log V)。
- 每个节点最多入队一次（当其
- 总时间复杂度主要由优先队列的操作决定：O(V log V + E log V)。
- 对于连通图，通常 E >= V-1。因此复杂度可以简化为 O(E log V)。如果使用斐波那契堆 (Fibonacci Heap) 作为优先队列，
decrease-key操作的摊销时间是 O(1)，提取最小是 O(log V)，总复杂度可以优化到 O(E + V log V)，这在理论上是更优的，尤其对于非常稀疏的图。但在实践中，二叉堆实现的 O(E log V) 通常已经足够快，并且实现更简单。
-
空间复杂度：
- 邻接表：O(V + E)
dist数组：O(V)- 优先队列：最坏情况下可能存储 O(E) 个元素（如果很多边都导致节点入队），但由于节点最多 V 个，且每个节点最终只会被有效处理一次，通常认为优先队列的大小与 V 相关，或者在最坏情况下是 O(E) 或 O(V)，取决于实现和图结构。一般记为 O(V) 或 O(E)。
- 总空间复杂度主要是 O(V + E)。
五、Dijkstra 算法的局限性
Dijkstra 算法虽然强大且常用，但它有一个重要的局限性：不能正确处理带有负权重边的图。
原因：如前所述，Dijkstra 算法的正确性基于贪心选择：一旦一个节点 u 被选为 dist 最小的节点并加入集合 S，算法就认为已经找到了从源点到 u 的最短路径，并且不会再更新 dist[u]。
如果图中存在负权重边，就可能出现以下情况：当前找到的到 u 的路径看似最短，但后续通过一条或多条负权重边，可能形成一条从源点经过某个尚未访问的节点 w，再到达 u 的更短路径。而 Dijkstra 算法一旦将 u 加入 S，就不会再考虑这种可能性，从而导致结果错误。
示例（负权边导致失败）：
B --(-3)--> C
/ /
(1)/ / (1)
/ /
A -----------
源点为 A。
- 初始化：
dist={A:0, B:∞, C:∞}, S={}, U={A,B,C} - 选 A：S={A}, U={B,C}。松弛邻居：
dist[B]=1.dist={A:0, B:1, C:∞} - 选 B：S={A,B}, U={C}。松弛邻居 C：
dist[B] + weight(B, C) = 1 + (-3) = -2。更新dist[C]=-2.dist={A:0, B:1, C:-2} - 选 C：S={A,B,C}, U={}. 算法结束。
结果：dist[C] = -2。
看起来没问题？考虑这个图：
B --(-3)--> C
/ ^
(1)/ /
/ / (1)
A --- (2) --> D
源点 A。
- 初始化：
dist={A:0, B:∞, C:∞, D:∞}, S={}, U={A,B,C,D} - 选 A：S={A}, U={B,C,D}。松弛邻居 B, D：
dist[B]=1,dist[D]=2.dist={A:0, B:1, C:∞, D:2} - 选 B：S={A,B}, U={C,D}。松弛邻居 C：
dist[B] + weight(B, C) = 1 + (-3) = -2。更新dist[C]=-2.dist={A:0, B:1, C:-2, D:2} - 选 C：S={A,B,C}, U={D}。松弛邻居 (无)。
dist={A:0, B:1, C:-2, D:2} - 选 D：S={A,B,C,D}, U={}。松弛邻居 C：
dist[D] + weight(D, C) = 2 + 1 = 3。3 > dist[C](-2)，不更新。
算法结束。结果：dist[C]=-2, dist[D]=2。
这里的 dist[C]=-2 是错误的！实际最短路径是 A -> D -> C，长度为 2 + 1 = 3。
错误发生在第 3 步选择 B 时。当时 dist[B]=1 是 U 中最小的。但实际上，存在一条更长的“中间”路径 A->D (长度2)，它能通往一个可以通过负权边大幅缩短距离的节点 C。Dijkstra 算法过早地确定了 B 的最短路径，并基于此计算了 C 的距离，未能发现 A->D->C 这条更优路径。
对于包含负权重边的图，需要使用其他算法，如 Bellman-Ford 算法 或 SPFA (Shortest Path Faster Algorithm)。Bellman-Ford 可以处理负权边，并且能检测出负权环（Negative Cycle，会导致最短路径无限小）。SPFA 是 Bellman-Ford 的一种队列优化版本，在实践中通常比 Bellman-Ford 更快，但最坏情况复杂度仍与 Bellman-Ford 相同。
六、Dijkstra 算法的应用
Dijkstra 算法因其高效和直观性，在众多领域都有广泛应用：
- 路由协议：如 OSPF (Open Shortest Path First) 协议，在网络路由器之间计算数据包传输的最短路径。路由器维护网络拓扑信息，运行 Dijkstra 算法确定到其他路由器的最佳路由。
- 地理信息系统 (GIS)：在地图软件（如 Google Maps, Waze）中计算两点之间的最快或最短驾车、步行、公交路线。道路可以看作图的边，交叉口是节点，权重可以是距离、预计通行时间（考虑交通状况）等。
- 社交网络分析：计算两个人之间的“关系距离”或信息传播的最短路径。
- 航班规划：寻找两个机场之间的转机次数最少或总飞行时间最短的航线。
- 生物信息学：在基因调控网络或蛋白质相互作用网络中寻找信号传导的最短路径。
- 资源分配与调度：在物流、运营研究等领域，优化资源（如车辆、人员）的调度路径。
- 游戏开发：计算游戏中角色（NPC）移动到目标位置的最短路径。
七、总结
Dijkstra 算法是解决单源最短路径问题的基石性算法，其核心在于贪心策略和松弛操作。通过维护一个已确定最短路径的节点集合，并利用优先队列等数据结构进行优化，它能在非负权重图上高效地找到从源点到所有其他节点的最短路径。
关键点回顾：
- 目标：找到非负权重图中单源最短路径。
- 核心思想：贪心选择当前距离最短的未访问节点，并用它来更新（松弛）其邻居节点的距离。
- 数据结构：邻接表（推荐）、距离数组
dist[]、优先队列（优化）。 - 复杂度：朴素实现 O(V^2)，优先队列优化后 O(E log V) 或 O(E + V log V)。
- 局限性：不能处理含负权重边的图。
- 应用：网络路由、地图导航、社交网络、物流规划等。
掌握 Dijkstra 算法不仅是理解图算法的基础，更是解决实际世界中许多优化问题的有力工具。希望通过本文的详细介绍，你已经对 Dijkstra 算法有了全面而深入的理解，真正做到“一文搞懂”。