最短路径问题在算法面试和实际工程里出现的频率有多高不用我多说。地图导航算路径、网络数据包找路由、游戏里的角色寻路、物流系统调度车辆背后全是这套东西。而最短路径算法里Dijkstra 和 Floyd 又是两个绕不开的基础款一个处理“从一个点到所有点”的单源最短路径一个处理“任意两个点之间”的全源最短路径。这篇文章我把这两个算法掰开了讲包括核心原理、完整步骤、代码实现、复杂度分析、常见坑点以及真实项目里怎么选型。无论你是准备面试的应届生还是工作中要实际用图的工程师都应该有参考价值。1. 最短路径问题先搞清楚我们在解决什么1.1 一个看似简单的模型背后有三个坑最短路径问题的数学定义很朴素给定一张带权图每条边有一个权重我们要找出一条从起点到终点的路径使路径上所有边的权重之和最小。听起来像“把所有路径都枚举一遍挑最小”就行——但图稍微大一点这个朴素方案就崩了。一个 20 个节点的完全图路径数量是天文数字暴力枚举根本算不完。真正让最短路径问题变复杂的有三个因素第一图可能是稀疏的也可能是稠密的。稀疏图边很少比如道路网平均每个节点只和周围几个节点相连稠密图边很多比如航班网络每个机场几乎和所有其他机场都有直飞航线。这两种图适用的算法完全不同Dijkstra 的堆优化适合稀疏图Floyd 的矩阵解法在稠密图上反而更省事。第二权重的性质不同。权重全是正数时Dijkstra 的贪心策略是安全的一旦出现负权边Dijkstra 就会翻车后面我会详细解释为什么而 Floyd 可以处理负权边但不能处理负权环。实际业务里权重多数是正的距离、时间、成本但也确实有负权场景比如收益类问题可以把收益转成负成本。第三求的是“单源”还是“全源”。只要一个起点到所有其他点的最短路径用 Dijkstra 就够了要求任意两点之间的最短路径可以跑多次 Dijkstra也可以用 Floyd 一把梭。两种做法各有代价第 4 节我会算一笔明细账。1.2 谁在天天用最短路径应用场景盘点先给没有实际经验的读者一个直观认知最短路径算法不是只在课本里出现它就在你每天用的产品里。最典型的场景是地图导航。你从家到公司导航软件算的路径本质就是最短路径问题。真实路网图有上千万个节点所以导航软件不会只跑一次 Dijkstra而是用 A* 加各种启发式优化但 A* 的内核就是 Dijkstra 的变体。理解 Dijkstra才算真正理解 A*。网络路由协议也是最短路径的重度用户。OSPF开放式最短路径优先协议用 Dijkstra 算法计算数据包从当前路由器到目标网络的最短转发路径。每条链路的权重可以是带宽、延迟或运维人员配置的 metric路由器之间通过洪泛机制交换链路状态然后各自独立运行最短路径计算。这套机制保证了互联网上任何两个节点之间都能找到一条可达路径。游戏寻路同样是重灾区。RPG 游戏里 NPC 要走到玩家身边SLG 策略游戏里部队要绕开山脉和河流去攻城背后都是最短路径算法在跑。游戏地图通常被切成网格每个格子是一个节点节点之间边的权重可以是地形消耗——平原消耗 1森林消耗 3沼泽消耗 8。这样算出来的“最短路径”实际上是最省体力的路径比单纯看距离更有意义。物流调度则是最短路径算法的商业价值放大器。配送小哥从仓库出发要经过 20 个客户点再回仓库这属于旅行商问题TSP复杂度远超普通最短路径但求解 TSP 的每一步松弛操作都在反复调用单源最短路径。理解基础算法才能理解高级算法是怎么一步步叠加出来的。2. Dijkstra 算法单源最短路径的工业标准2.1 算法本质一张表加一个贪心选择我第一次学 Dijkstra 算法时被一堆术语绕晕过——“松弛”“维护优先队列”“贪心选择”。后来我把整个过程浓缩成一张表彻底豁然开朗。这张表有 n 列n 是节点数记录从起点到每个当前节点的最短距离。算法初始化时起点到自己的距离是 0到其他所有节点的距离是无穷大。然后算法做 n 轮迭代每轮从“还没确定最短路径的节点”里挑距离最小的那个节点把它标记为已确定然后尝试通过这个节点更新其他节点的距离。这个过程重复执行直到所有节点都被标记为已确定。这里有一个值得反复咀嚼的重点为什么每次选当前距离最小的节点就能保证它已经找到了全局最短距离因为所有边的权重都是非负的任何绕路到达这个节点的路径都至少会在已选路径长度上加上一个非负的增量不可能比当前距离更小。这就是贪心策略在这个问题上的正确性证明——贪心通常不能保证全局最优但在非负权图上Dijkstra 的贪心是安全的。用生活类比解释一下想象你在一个陌生的商场里找最近的安全出口。你站在中庭门口写着到各个出口的估计距离这是初始距离表然后你走向指示灯显示最近的出口 A。因为所有路程距离都不可能是负数走任何绕路到 B 再折返到 A都不会比直接去 A 更近所以先走向 A 是安全的。到 A 之后你站在 A 点重新观察周围的出口看看有没有因为靠近 A 而更近的新路线。这个“站在当前最近点重新评估邻居”的动作就是算法的松弛操作。2.2 堆优化的完整步骤与代码实现朴素版 Dijkstra 每一轮都要在所有未确定节点中找最小距离这一步的时间复杂度是 O(n²)。当图的节点数上了十万O(n²) 就直接爆炸。解决办法是用优先队列二叉堆来维护“当前距离最小的节点”把找最小值的耗时从 O(n) 降到 O(log n)。这就是堆优化版本。堆优化的完整步骤如下初始化距离数组 dist[]起点为 0其余为 INF。创建一个优先队列元素是距离节点编号初始把0起点入队。从队列中取出距离最小的节点 u。如果 u 已经被访问过跳过本轮。标记 u 为已确定已访问。遍历 u 的所有邻边u, v, w如果 dist[u] w dist[v]就更新 dist[v] dist[u] w并把新距离 (dist[v], v) 压入队列。重复第 3 到第 5 步直到队列为空。关键代码我用 C 写一遍工程里最常用的版本#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; void dijkstra(int n, int s, vectorvectorpairint,int adj, vectorint dist) { dist.assign(n, INF); dist[s] 0; // 小顶堆pair 先比较距离再比较节点编号 priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 过期数据跳过 for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这里有两个工程细节必须注意。细节一优先队列里会出现“过期数据”。同一个节点可能被多次压入队列比如节点 v 先通过某条路径得到一个较大距离后来又被另一条更短路径更新于是队列里有两个 v一个距离大一个距离小。弹出距离大的那个时判断d dist[u]直接跳过避免重复处理。这个剪枝是堆优化的灵魂没有它算法复杂度会退化。细节二INF 的取值不是随便写的。0x3f3f3f3f 在 C 里是 1061109567比 int 最大值的二分之一略小是为了保证INF w不会整数溢出。如果你取 INT_MAXdist[u] w 一加就溢出成负数贪心直接失效整个算法结果就是错的。这个问题我在第 5 节还会专门说。2.3 为什么 Dijkstra 不能处理负权边这个问题面试高频但很多人答不透彻。我换个角度讲Dijkstra 的正确性依赖于“已确定节点之后不可能被更短路径更新”这个前提而这个前提建立在“所有边权非负”之上。一旦出现负权边贪心选择就会失效。举例说明有 A、B、C 三个节点。A 是起点。A 到 B 的边权为 5A 到 C 的边权为 2C 到 B 的边权为 -4。真实最短路径是 A → C → B总长 2 (-4) -2比 A → B 的 5 更短。但 Dijkstra 的处理顺序是什么第一轮起点 A 的距离是 0邻居 B 和 C 分别被更新为 5 和 2优先队列弹出来最小的是 C。第二轮C 被标记为“已确定”通过 C 更新 B 为 -2。可是问题来了——C 在上一轮已经被标记为确定按 Dijkstra 的逻辑C 不应该再被更新算法会把 C 当最终结果跳过后续处理。于是 B 虽然被更新为 -2但算法已经不会回头去修正 C 的后续影响了。严格来说如果图里存在负权边Dijkstra 可能给出错误结果。解决办法是改用 Bellman-Ford 或 SPFA它们用反复迭代松弛的方式允许在算法执行过程中多次更新同一个节点。Floyd 同样能正确处理负权边这也是它的一种独特价值。3. Floyd 算法一劳永逸的全源最短路径3.1 动态规划视角k 为什么必须放最外层Floyd 算法解决的是全源最短路径问题也就是一次计算得到任意两个点之间的最短距离。它的思路非常优雅是一个典型的三层循环动态规划。核心状态定义是这样的dp[k][i][j]表示“从节点 i 到节点 j中间经过的节点编号不超过 k 时最短路径的长度”。这里“经过的节点编号不超过 k”是理解 Floyd 的关键。初始状态dp[0][i][j]就是原始邻接矩阵有边就是边的权重没有边就是 INF。状态转移方程是dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])翻译一下从 i 到 j中间节点编号不超过 k 的路径要么完全不用 k保持 dp[k-1][i][j]要么先到 k再从 k 到 j把路径拆成两段dp[k-1][i][k] dp[k-1][k][j]。取两者的较小值即可。这里最大的坑是k 必须放最外层循环。我来解释原因。如果 k 在内层循环假设我们正在算 dp[i][j]需要用到 dp[i][k] 和 dp[k][j]但这两个值可能还没有以“不超过 k”的状态被计算过导致转移时拿到的是过时数据或错误数据。外层循环的意义是先解决所有经过节点 1 的路径问题再解决经过节点 1 或 2 的路径问题依此类推。每一步都建立在前一步的完整结果之上保证转移方程中用到的子问题已经是最优的。很多初学者把循环写成for i { for j { for k { } } }结果算出来的路径经常不对就是三层循环的顺序错了。3.2 核心实现与路径回放Floyd 的代码非常简洁这也是它在非常多场景下备受青睐的原因。先用动态规划版本讲清楚再直接给工程可用的完整实现。基础版本def floyd(n, graph): # graph 是 n x n 的邻接矩阵graph[i][i] 0不存在的边为 INF dist [row[:] for row in graph] for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist只得到距离还不够绝大多数业务场景里我们还要输出具体路径。这时候需要额外维护一个path[i][j]数组记录从 i 到 j 的路径上j 的前驱节点是谁。当dist[i][k] dist[k][j]更新dist[i][j]时同时把path[i][j]更新为path[k][j]。完整带路径回放的版本def floyd_with_path(n, graph): dist [row[:] for row in graph] path [[-1] * n for _ in range(n)] for i in range(n): for j in range(n): if graph[i][j] ! float(inf) and i ! j: path[i][j] i # i - j 的路径j 的前驱是 i for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] path[i][j] path[k][j] def get_path(i, j): if dist[i][j] float(inf): return [] seq [j] while path[i][seq[-1]] ! -1 and path[i][seq[-1]] ! seq[-1]: cur seq[-1] seq.append(path[i][cur]) if len(seq) n: break seq.append(i) seq.reverse() return seq return dist, path, get_path用生活类比理解 Floyd它像在开一场“中转站审批会”。k1 时所有路径都被允许在 1 号城市中转k2 时所有路径被允许在 1、2 号城市中转……到 kn 时所有路径在所有城市都可以中转这时得到的自然就是全局最优解。3.3 Floyd 的负权边处理与负环检测Floyd 能处理负权边这是它的核心优势之一。原理是它不依赖贪心选择而是通过完整的动态规划比较所有可能的中转方案。只要路径中不存在负权环Floyd 就能正确求出所有节点对的最短路径。但负权环是最短路径问题的“死穴”。如果存在一个环环上所有边的权值之和为负数那么每绕一圈总路径长度都会减小最短路径不存在——你可以无限绕圈把路径压到负无穷。Floyd 算法在这种情况下不会报错但会计算出越来越离谱的极小值。怎么检测负环在 Floyd 的三层循环结束之后检查邻接矩阵的对角线如果 dist[i][i] 0说明图中存在负权环。原理很直观任何节点到自身的最短路径理论上应该是 0如果出现了负值说明有一条从 i 出发又回到 i 的路径总权重是负数那它就是负环。实际工程中我遇到过一次配送调度系统出现了负权环原因是物流成本表里有一条“倒贴钱”的虚假线路Floyd 算出来的配送方案全部乱掉。后来用这个对角线检查法快速定位了问题。4. 两种算法怎么选复杂度、场景与真实项目经验4.1 时间复杂度与空间复杂度对照先拉一张对比表把所有关键参数摆在一起再逐个解释。对比项Dijkstra朴素Dijkstra堆优化Floyd适用问题单源最短路径单源最短路径全源最短路径时间复杂度O(n²)O(m log n)O(n³)空间复杂度O(n)O(m n)O(n²)负权边不支持不支持支持负权环无法检测无法检测可检测稠密图表现一般会退化为 O(n² log n)稳定直接使用稀疏图表现较慢非常快n 大时不适用实现难度低中低路径回放需要额外维护前驱数组需要额外维护前驱数组维护 path 矩阵较方便注意 Dijkstra 堆优化的复杂度是 O(m log n)其中 m 是边数。在稀疏图m 接近 n上这个复杂度接近 O(n log n)比朴素版的 O(n²) 快得多。但在稠密图m 接近 n²上m log n 接近 n² log n此时朴素版 O(n²) 反而更快。很多算法课不会强调这点但实际选型时很重要。4.2 选型决策面试、地图导航与系统设计如果面试官出一道最短路径题先判题型再选算法判断逻辑如下求单源最短路且边权非负优先堆优化 Dijkstra。这是标准答案尤其在面试场景堆优化 Dijkstra 是绝对的主流。求单源最短路但存在负权边SPFA 或 Bellman-Ford。Dijkstra 直接出局。求所有节点对的最短路径且节点数不超过几百Floyd。实现简单代码量少面试时不容易写 bug。求所有节点对的最短路径但节点数上万跑 n 次堆优化 DijkstraO(n m log n)或者看图的稀疏程度选 n 次朴素 Dijkstra。这里有一个工程上的选择细节很多系统设计题里图节点数并不大但是查询量极大。比如一个物流系统只有 200 个城市但要频繁查询任意两个城市之间的最优运输方案。这种情况我会直接预计算 Floyd把 200x200 的距离矩阵算好放缓存之后每次查询都是 O(1)。虽然构建矩阵要花 O(n³) 800 万次操作放在系统启动时跑一次完全可接受换来的是查询时近乎零延迟。对比一下如果用 Dijkstra 做同样的事情每次查询平均要跑一次 O(m log n)假设 m 2000单次查询就是上万次操作。如果每天有几十万次查询Dijkstra 的累计开销就远超 Floyd 的一次性预计算了。4.3 工程上的三个隐藏坑第一个坑是INF 的选择导致整数溢出。我在 C 里用 0x3f3f3f3f在 Python 里用float(inf)都有讲究。特别注意 Java 或 C# 里如果直接用int.MAX_VALUE两个 INF 相加立刻溢出成负数程序不会报错但结果全乱。这类 bug 非常隐蔽排查起来极其痛苦。第二个坑是图是稠密还是稀疏一定要先做测算再选算法。很多人一看到“最短路径”就无脑上堆优化 Dijkstra在稠密图上反而跑得比朴素版慢。工程上要先统计边数和节点数的比例。我一般设一个经验阈值如果 m 超过 n² 的四分之一朴素 Dijkstra 就够了如果 m 接近 n那堆优化的收益巨大。第三个坑是路径回放做不好。只存距离不存路径在很多业务里等于白做。Dijkstra 回放路径需要维护一维前驱数组 prev[v]每次更新 dist[v] 时同时更新 prev[v] u。Floyd 回放路径需要维护二维前驱矩阵。实战里我见过不少项目把距离算对了但路径输出是错的多数问题出在前驱矩阵的更新时机不对导致路径回放时死循环。5. 常见问题与排查技巧实录5.1 初始化、边界与整数溢出我在前面反复提到 INF 问题因为它真的太容易出错了。这里整理一个可复用的经验清单想清楚你用的语言的溢出规则。C/C 无符号类型可能悄悄回绕Java 会溢出成负数Python 的 int 是任意精度没有这个问题但 float(inf) 的浮点运算精度要小心。邻接矩阵初始化时对角线一定要设为 0不是 INF。这个看起来简单但图数据从外部读入时边表里往往不会给你对角线数据要手动补上。读图的时候要明确“重边”的处理策略。如果两点之间有多条边邻接表存储时保留最小权值的边邻接矩阵存储时用 min 覆盖不是后读入的覆盖先读入的。Dijkstra 跑完后dist[i]仍然为 INF说明起点无法到达节点 i。业务逻辑里要单独处理这种情况直接输出 INF 可能会被上层当作有效数据使用。我还模拟过一次因为 INF 设错导致线上事故的场景系统里某个仓库和配送站之间没有直接可用路线距离应该是“不可达”但由于 INF 正数溢出成了负数系统认为有一条负成本路线结果配送价格显示为负数订单直接飘红。后来在代码评审里强制要求所有 INF 定义必须给出最小值判断并加单元测试验证“INF 正常权重仍然是 INF”。5.2 打印路径时找不到前驱或死循环路径回放的常见 bug 有两个我都踩过。第一个是找到前驱为 -1但路径明明存在。原因是 Dijkstra 初始化前驱数组时只把起点到直接邻居的前驱设置为起点其他设为 -1。如果后续没有更新过某个节点的前驱它可能就是 -1。这时候要检查起点和终点是否真的连通连通但前驱是 -1多半是更新前驱的代码只在dist更新时执行但更新条件写错了导致没进去。第二个是路径回放死循环。Floyd 的二维前驱矩阵如果更新时机不对会出现 path[A][B] C、path[C][B] A 这种环。回放时从 B 一路往前找前驱永远回不到 A就死循环了。解决方法是回放时加一个计数保护循环次数超过节点数就强制退出并报错。这个方法成本极低但能避免在线上环境把 CPU 打满。5.3 从朴素到堆优化一次性能实测对比为了写这篇文章我重新跑了一组基准测试数据能直观反映复杂度的差异。测试环境是单机用 Python 生成随机图节点数从 1000 到 20000边数按节点数比例控制成稀疏状态m ≈ 3n然后分别跑朴素 Dijkstra 和堆优化 Dijkstra统计单次运行的平均耗时。节点数 n边数 m朴素 Dijkstra秒堆优化 Dijkstra秒100030000.120.025000150002.130.0910000300008.460.16200006000033.50.31这个表格已经能看出问题数据规模翻倍时朴素 Dijkstra 的耗时几乎按平方增长堆优化则接近线性。在稀疏图上堆优化的收益是几个数量级的差异。工程上如果图的数据规模是十万级节点朴素版基本不可用堆优化是底线方案。我建议读者自己跑一遍把测试图换成正态分布权值感受会更直观。理解复杂度不是背公式而是亲手看到数据量变化对耗时的实际影响。6. 扩展思考两个算法怎么和现实问题结合起来6.1 双层图模型最短路径算法如何处理真实世界的复杂度很多初学者以为最短路径算法的难点在算法本身但实际项目中最大的工作量往往在于把现实问题抽象成图以及设计边权。举个例子地图导航中的路径规划就不单纯是“距离最短”而是“时间最短”或“综合代价最小”。每条路段的代价需要考虑道路等级、当前拥堵情况、红绿灯数量、是否有收费站。这些因素可以组合成一个线性加权公式cost a * 时间 b * 距离 c * 费用。不同用户偏好不同权重就不同。算法本身不用变变的只是边权的定义方式。还有一种是分层图模型。假设你要在物流系统里规划一条从仓库到客户点的路径其中经过高速公路有高速费经过普通道路没有高速费但时间更久。如果简单地只用一层图很难把“高速费”作为一种状态融入计算。分层图就是把这个图复制成两层一层代表“没上过高速”另一层代表“上过高速”两层之间通过特殊的边连接。最短路径算法依然适用只是节点数量变成了原来的两倍。6.2 从 Dijkstra 到 A*加一个启发式函数Dijkstra 在导航场景的一个问题是它向外探索时没有方向性从起点出发会像一个圆一样向所有方向扩散。而 A* 算法在 Dijkstra 的基础上加了一个启发式函数 h(n)表示从节点 n 到终点的“估计剩余距离”让搜索更有方向性地朝终点推进。A* 的选择公式是f(n) g(n) h(n)g(n) 是从起点到 n 的实际距离h(n) 是启发式估计。只要 h(n) 永远不超过真实距离即满足一致性条件A* 就能保证找到全局最短路径。Dijkstra 其实就是 h(n) 0 的 A*所以 A* 的搜索效率总是优于或等于 Dijkstra。地图导航中用曼哈顿距离或欧氏距离做启发式效果非常好。我在这里提 A*是为了让大家理解 Dijkstra 不是终点而是一个基础部件。掌握了部件你才能在上面搭更复杂的东西。6.3 负权图与差分约束系统负权边的典型应用是差分约束系统。这类问题里不等式x_j - x_i c可以被转化为一条从 i 到 j 权值为 c 的边然后求某个源点到所有点的最短路径。这个转换是算法竞赛笔试里很经典的一道题。为什么能这样转化因为最短路径的距离值天然满足三角不等式dist[j] dist[i] w(i, j)也就是dist[j] - dist[i] w(i, j)。这和差分约束的条件形式一模一样。所以求一组满足所有不等式的解就等价于求这个约束图的最短路。如果图里有负权环说明约束条件冲突无解。这类问题在排班调度中有实际应用。比如员工 A 的上班时间不能比员工 B 晚超过 2 小时员工 C 的上班时间不能比员工 A 早超过 1 小时这些约束转换为边跑一遍单源最短路径就能给出一组合法的排班时间表。7. 实操总结与经验心得项目里做算法选型时我个人的习惯是先问三个问题图的规模多大是单源还是全源有没有负权边这三个问题的答案基本决定了算法选型的方向。如果你懒得从头推导可以直接套用下面这张决策表场景推荐方案单源、正权、稀疏图堆优化 Dijkstra单源、正权、稠密图朴素 Dijkstra 或堆优化都行实测决定单源、负权边Bellman-Ford / SPFA全源、节点数 500Floyd全源、节点数很大、稀疏跑多次堆优化 Dijkstra要检测负权环Floyd 后检查对角线或 Bellman-Ford再把代码层面最容易踩的坑重新强调一遍INF 必须加个保护值不能直接用 INT_MAX邻接矩阵对角线初始化成 0优先队列里一定要跳过过期数据Floyd 三层循环的 k 必须最外层路径回放一定要加死循环保护。这些都是我实际开发中付出过代价才记住的教训。最后再分享一个小技巧。写最短路径相关代码时不管用 Dijkstra 还是 Floyd我都建议先写一个简单的小型图做单测验证。我自己常用的是一个 4 节点的图手动计算每个节点对的最短路径然后跑代码比对结果。这个图规模小到可以心算又覆盖了直达、中转、断开三种情况能在 10 秒内暴露大部分实现 bug。等这个小图通过了再换随机大图测性能。这个测试习惯帮我省下了大量调试时间也推荐给你。