1. 从一个"找路"问题说起：Dijkstra到底在解决什么

很多人第一次接触Dijkstra算法，是在数据结构或者图论的课上，老师画一张带权重的图，然后让你从A点开始，一步步标号，最后得出到每个点的最短距离。当时觉得好像也不难，但真到自己写代码的时候，就发现各种问题冒出来了：优先队列怎么用？为什么不能处理负权边？松弛操作到底在干什么？路径怎么还原？

我当初也是这样，课本上的伪代码看懂了，但一落到实际代码就卡壳。后来做了几个路径规划相关的项目，才慢慢把这块吃透。这篇文章就把我对Dijkstra算法的理解完整地梳理一遍，从核心思想到代码实现，从手算模拟到工程优化，尽量做到"简单易懂"这四个字。

Dijkstra算法本质上解决的是单源最短路径问题：给定一个带权图和一个起点，求出起点到其他所有节点的最短路径长度。它的应用场景非常广，比如地图导航中的路线规划、网络路由中的数据包转发、游戏中的AI寻路等等。只要你能把问题抽象成"节点+带权边"的模型，Dijkstra就能派上用场。

这篇文章适合谁看？如果你是正在学算法的学生，或者工作中需要用到路径规划的开发者，又或者你只是想把Dijkstra彻底搞明白，那这篇内容应该能帮到你。我会从最基础的概念讲起，逐步深入到代码实现和优化技巧，中间穿插我自己踩过的坑和总结的经验。

2. 核心思想拆解：贪心策略为什么能work

2.1 用生活场景理解Dijkstra的贪心逻辑

Dijkstra的核心是贪心策略。什么叫贪心？就是每一步都选当前看起来最优的那个选项，然后基于这个选择继续往下走。

举个生活中的例子。假设你要从家出发去城市的各个地方，你手里有一张地图，上面标了每两个地点之间的距离。你想知道从家到每个地方的最短距离。Dijkstra的做法是这样的：

1. 一开始，你只知道家到自己距离是0，到其他地方的距离都未知（记为无穷大）。
2. 你从"未确定最短距离"的地点中，选一个当前已知距离最小的。显然一开始就是家自己。
3. 以这个点为跳板，看看通过它能不能让其他地点的距离变短。比如家到超市直接走是10公里，但家先到学校再超市是6公里，那就更新超市的距离为6。
4. 重复第2步和第3步，直到所有地点的最短距离都确定。

这个过程中，每次选的都是"当前已知距离最小"的那个点，这就是贪心的体现。那为什么这样做是对的？关键在于边权非负这个前提。

2.2 为什么边权不能为负：一个反例就够了

如果图中有负权边，Dijkstra的贪心策略就会失效。我举一个具体的例子来说明。

假设有三个节点A、B、C。A到B的边权是1，A到C的边权是5，B到C的边权是-10。按照Dijkstra的流程：

• 第一步：确定A的最短距离为0。
• 第二步：从B和C中选距离最小的。B的距离是1，C的距离是5，所以选B，确定B的最短距离为1。
• 第三步：以B为跳板，更新C的距离。通过B到C的距离是1+(-10)=-9，比原来的5小，所以C的距离更新为-9。
• 第四步：确定C的最短距离为-9。

看起来没问题？但问题在于，如果存在一条路径A→C→B，而C到B的边权也是负的，那B的最短距离可能在确定之后还能被更新，这就和"确定"这个词矛盾了。Dijkstra的核心假设是：一旦一个节点被选为"当前距离最小"并确定下来，它的最短距离就不会再变了。这个假设在边权非负时成立，因为任何绕路都会增加总距离；但有了负权边，绕路反而可能减少总距离，假设就不成立了。

注意：如果你的图里存在负权边，应该考虑Bellman-Ford算法或者SPFA算法，它们能处理负权边，但时间复杂度会更高。

2.3 松弛操作：Dijkstra的心跳

Dijkstra算法中最核心的操作叫松弛（Relaxation）。这个词听起来有点抽象，但理解起来很简单。

假设我们已知起点到节点u的最短距离是dist[u]，u到v有一条边，权重是w。那么从起点经过u到v的距离就是dist[u] + w。如果这个值比当前记录的dist[v]小，我们就更新dist[v]，这就叫"松弛"。

你可以把松弛想象成一根绷紧的橡皮筋。dist[v]初始是无穷大，相当于橡皮筋拉得很长。每次找到一条更短的路径，橡皮筋就松一点，直到最后绷到最短的那个位置。

松弛操作的伪代码大概是这样：

if dist[u] + w < dist[v]: dist[v] = dist[u] + w prev[v] = u # 记录前驱节点，用于还原路径

这个操作看起来简单，但它是整个算法的基石。每一次从优先队列中取出一个节点，都要对它所有的邻居尝试松弛。如果松弛成功，就把邻居加入优先队列（或者更新它在队列中的值）。

2.4 朴素实现 vs 优先队列优化：差距有多大

Dijkstra有两种常见的实现方式：朴素实现和优先队列优化。

朴素实现的思路是：用一个数组记录所有未访问节点的距离，每次线性扫描找到距离最小的那个。时间复杂度是O(V²)，其中V是节点数。这种实现适合稠密图，也就是边数接近V²的图。

优先队列优化的思路是：用一个最小堆来维护未访问节点的距离，每次从堆顶取出距离最小的节点。时间复杂度是O((V+E)logV)，其中E是边数。这种实现适合稀疏图，也就是边数远小于V²的图。

我实测下来的感受是：对于节点数在1000以内的图，两种实现的差距不太明显；但当节点数上万时，优先队列优化的优势就非常明显了。下面这张表可以帮你快速判断该用哪种：

实操心得：大多数工程场景下，优先队列优化已经足够好了。斐波那契堆虽然理论复杂度更低，但常数因子大，实际性能未必更好，而且实现复杂，不建议新手尝试。

3. 手把手实现：从伪代码到可运行代码

3.1 图的存储方式：邻接矩阵还是邻接表

在写代码之前，首先要决定怎么存图。常见的方式有两种：邻接矩阵和邻接表。

邻接矩阵用一个二维数组graph[i][j]表示节点i到节点j的边权。如果两个节点之间没有边，就设为无穷大。这种方式的优点是查询两点之间是否有边非常快，O(1)时间；缺点是空间复杂度是O(V²)，对于稀疏图来说很浪费。

邻接表用数组+链表（或者vector）的方式存储每个节点的邻居。graph[i]是一个列表，里面存着所有从i出发的边，每条边包含目标节点和权重。空间复杂度是O(V+E)，对于稀疏图非常友好。

我个人的选择习惯是：如果节点数不超过1000，直接用邻接矩阵，写起来简单；如果节点数很大，或者边很稀疏，就用邻接表。下面用Python演示邻接表的构建：

# 邻接表构建示例 n = 5 # 节点数 edges = [ (0, 1, 10), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 1, 4), (2, 3, 8), (2, 4, 2), (3, 4, 7), (4, 3, 9) ] graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w))

这段代码构建了一个有5个节点、9条边的有向图。graph[u]里面存的是所有从u出发的边，每条边是一个(目标节点, 权重)的元组。

3.2 优先队列优化的完整实现

下面是一个完整的Dijkstra实现，用优先队列优化，附带路径还原功能：

import heapq def dijkstra(graph, start): """ graph: 邻接表，graph[u] = [(v, w), ...] start: 起点 返回: dist数组和prev数组 """ n = len(graph) INF = float('inf') dist = [INF] * n prev = [-1] * n dist[start] = 0 # 优先队列，存储(距离, 节点) pq = [(0, start)] visited = [False] * n while pq: d, u = heapq.heappop(pq) # 如果这个节点已经处理过，跳过 if visited[u]: continue visited[u] = True # 遍历所有邻居，尝试松弛 for v, w in graph[u]: if not visited[v] and dist[u] + w < dist[v]: dist[v] = dist[u] + w prev[v] = u heapq.heappush(pq, (dist[v], v)) return dist, prev def get_path(prev, start, end): """还原从start到end的路径""" path = [] cur = end while cur != -1: path.append(cur) cur = prev[cur] path.reverse() if path[0] == start: return path return [] # 不可达

这段代码有几个关键点需要说明：

第一，visited数组的作用是标记已经确定最短距离的节点。为什么需要它？因为优先队列中可能存在同一个节点的多个条目（每次松弛成功都会push一个新的），如果不加判断，同一个节点可能被处理多次，虽然不影响正确性，但会浪费时间。

第二，heapq是Python内置的最小堆实现。它存储的是(距离, 节点)的元组，Python会比较元组的第一个元素，所以距离最小的会排在堆顶。

第三，路径还原通过prev数组实现。每次松弛成功时，记录prev[v] = u，表示v的最短路径是从u过来的。最后从终点往回追溯，就能得到完整路径。

3.3 手算模拟：用一个具体例子走一遍

光看代码可能还不够直观，我们用一个具体的图来手动模拟一遍Dijkstra的执行过程。

假设有5个节点，编号0到4，边的情况如下：

0 -> 1: 10 0 -> 2: 3 1 -> 2: 1 1 -> 3: 2 2 -> 1: 4 2 -> 3: 8 2 -> 4: 2 3 -> 4: 7 4 -> 3: 9

起点是0。初始化：dist = [0, ∞, ∞, ∞, ∞]，优先队列 = [(0, 0)]。

第一轮：取出(0, 0)，标记0为已访问。遍历0的邻居：

• 到1：0+10=10 < ∞，更新dist[1]=10，prev[1]=0，入队(10, 1)
• 到2：0+3=3 < ∞，更新dist[2]=3，prev[2]=0，入队(3, 2)

此时dist = [0, 10, 3, ∞, ∞]，队列 = [(3, 2), (10, 1)]。

第二轮：取出(3, 2)，标记2为已访问。遍历2的邻居：

• 到1：3+4=7 < 10，更新dist[1]=7，prev[1]=2，入队(7, 1)
• 到3：3+8=11 < ∞，更新dist[3]=11，prev[3]=2，入队(11, 3)
• 到4：3+2=5 < ∞，更新dist[4]=5，prev[4]=2，入队(5, 4)

此时dist = [0, 7, 3, 11, 5]，队列 = [(5, 4), (7, 1), (10, 1), (11, 3)]。

第三轮：取出(5, 4)，标记4为已访问。遍历4的邻居：

• 到3：5+9=14 > 11，不更新。

此时dist不变，队列 = [(7, 1), (10, 1), (11, 3)]。

第四轮：取出(7, 1)，标记1为已访问。遍历1的邻居：

• 到2：已访问，跳过
• 到3：7+2=9 < 11，更新dist[3]=9，prev[3]=1，入队(9, 3)

此时dist = [0, 7, 3, 9, 5]，队列 = [(9, 3), (10, 1), (11, 3)]。

第五轮：取出(9, 3)，标记3为已访问。遍历3的邻居：

• 到4：已访问，跳过

队列中剩下的(10, 1)和(11, 3)对应的节点都已经访问过了，会被跳过。

最终结果：dist = [0, 7, 3, 9, 5]。从0到4的最短距离是5，路径是0→2→4。

这个手算过程建议你自己在纸上画一遍，画完之后对Dijkstra的理解会深刻很多。

3.4 路径还原的细节与常见错误

路径还原看起来简单，但有几个容易出错的地方。

第一个坑是prev数组的初始化。我习惯初始化为-1，表示没有前驱。但在还原路径时，如果起点到终点不可达，追溯过程中会遇到-1，这时候需要判断路径是否有效。

第二个坑是路径方向。从终点往回追溯得到的路径是反的，需要reverse一下。这个虽然简单，但写代码时容易忘。

第三个坑是多条最短路径。如果存在多条距离相同的最短路径，Dijkstra只会记录其中一条（取决于松弛的顺序）。如果你需要所有最短路径，那就不能只用prev数组，需要用列表记录所有可能的前驱。

实操心得：在实际项目中，我通常会把dist和prev封装成一个结果对象返回，这样调用方用起来更方便。另外，如果只需要最短距离不需要路径，可以省掉prev数组，节省一点空间。

4. 工程实践中的优化与避坑指南

4.1 性能优化：什么时候该考虑更快的方案

虽然优先队列优化的Dijkstra已经能应付大多数场景，但在一些极端情况下，你可能需要更快的方案。

场景一：只需要起点到终点的最短路径，不需要到所有点的。这时候可以用A算法，它引入了一个启发式函数来引导搜索方向，通常比Dijkstra快很多。A的核心思想是：优先队列的排序依据从dist[u]变成dist[u] + h(u)，其中h(u)是u到终点的估计距离。只要h(u)不超过真实距离，A*就能保证找到最短路径。

场景二：图非常大，但只需要近似最短路径。这时候可以考虑一些近似算法，比如Landmark-based的算法，或者收缩层次（Contraction Hierarchies）。这些算法在导航系统中很常用，能在毫秒级处理全国级别的路网。

场景三：需要频繁查询不同起点的最短路径。如果图的结构不变，只是查询的起点不同，可以预处理一些数据结构，比如所有点对的最短路径（Floyd-Warshall算法），或者建立一些索引来加速查询。

不过话说回来，大多数业务场景下，优先队列优化的Dijkstra已经够用了。我做过一个节点数约5万、边数约20万的路网查询，用优先队列优化的Dijkstra，单次查询大概在几十毫秒级别，完全能满足实时性要求。

4.2 常见问题排查速查表

在实际写Dijkstra的过程中，我遇到过各种各样的问题。下面整理了一个速查表，方便你快速定位问题：

其中最常见的问题是优先队列没有去重导致死循环。这个问题的根源是：每次松弛成功都会往队列里push一个新条目，如果不加控制，同一个节点可能被反复处理。解决方法有两种：一是加visited数组，处理过的节点直接跳过；二是在取出节点时判断if d > dist[u]: continue，这样过期的条目会被忽略。

4.3 边界情况处理：空图、单节点、不可达

写算法的时候，边界情况往往是最容易出bug的地方。Dijkstra也不例外。

空图：如果图里没有节点，直接返回空结果就行。但要注意，有些实现会在初始化时访问graph[start]，如果start越界就会报错。所以最好先判断一下节点数。

单节点：如果图里只有一个节点，最短距离就是0，路径就是它自己。这个情况一般不会出问题，但如果你在还原路径时没有处理好，可能会返回空列表。

不可达节点：如果起点到某个节点没有路径，dist值会保持为无穷大。在输出结果时，需要把无穷大转换成一个可读的表示，比如-1或者"不可达"。

起点就是终点：这种情况最短距离是0，路径是只包含起点的一个列表。有些实现会返回空列表，这是不对的，需要注意。

注意：在工程代码中，我建议对输入做基本的校验，比如检查起点是否在合法范围内，图是否为空等。这些校验虽然简单，但能避免很多莫名其妙的bug。

4.4 与其他最短路径算法的对比选型

Dijkstra不是唯一的最短路径算法，不同的场景适合不同的算法。下面做一个简单的对比：

选择建议：如果没有负权边，优先用Dijkstra；如果有负权边，用Bellman-Ford或SPFA；如果需要所有点对的最短路径，且节点数不多，用Floyd-Warshall；如果只需要起点到终点的路径，且能设计出好的启发函数，用A*。

我个人的经验是：Dijkstra是使用频率最高的，基本上能覆盖80%以上的场景。剩下的20%里，A*和Floyd-Warshall各占一半。Bellman-Ford和SPFA用得比较少，主要是因为大多数实际问题的边权都是非负的。

4.5 实际项目中的应用案例

最后分享一个我在实际项目中的应用案例。之前做过一个物流配送的路径规划系统，需要计算配送中心到各个配送点的最短路径。图的结构是：节点是配送点和路口，边是道路，权重是道路长度或者预计通行时间。

这个项目的节点数大概在3万左右，边数在10万左右。一开始用的是朴素实现，单次查询要好几秒，完全没法用。后来改成优先队列优化，单次查询降到了50毫秒以内。再后来发现很多查询的起点是固定的（都是配送中心），就做了一些预处理，把常用起点的结果缓存起来，进一步降到了10毫秒以内。

这个项目让我深刻体会到：算法本身的优化很重要，但结合业务特点做针对性的优化同样重要。有时候一个简单的缓存就能带来数量级的提升。

另外一个坑是权重的动态变化。道路的通行时间会随着交通状况变化，如果每次变化都重新计算所有路径，开销太大。我们的做法是：只对受影响的区域重新计算，其他区域沿用缓存结果。这个策略虽然不能保证全局最优，但在实际业务中已经足够好了。

5. 写在最后：几个让我少走弯路的小技巧

Dijkstra这个算法，我前前后后学了三四遍，每次都有新的理解。最开始是死记硬背伪代码，后来是照着模板写代码，再后来是理解背后的贪心思想和松弛操作，最后是在实际项目中不断调优。如果你也在学这个算法，我建议你不要只停留在"能写出来"的层面，多问问自己"为什么这样写是对的"、"换个场景还适用吗"。

几个具体的小建议：第一，手算模拟至少走两遍，一遍简单的图，一遍稍微复杂的图，这样能帮你建立直觉；第二，代码实现至少写两遍，一遍朴素版，一遍优先队列版，对比一下差异；第三，找一个实际的小项目练手，比如做一个简单的地图寻路Demo，把算法用起来，比单纯刷题效果好得多。

还有一个容易被忽略的点：测试用例的设计。很多人写完Dijkstra只测一个简单的图就完事了，但实际上边界情况才是最容易出bug的地方。我通常会准备这样几组测试：单节点图、两点一边的图、有环的图、不可达的图、多条最短路径的图。这几组测下来，基本能覆盖大多数问题。

如果你在实现过程中遇到了什么奇怪的问题，欢迎一起交流。算法这东西，一个人闷头想容易钻牛角尖，多和别人讨论讨论，往往能豁然开朗。