★ FEATURED ARTICLE 前阵子帮一个团队看园区导览的小项目刚开始图上只有几十个点位最短路这块完全没人当一回事。等数据源里的监控点位一接进来节点凭空多出六七倍原来那套直接全源预计算的方案开始卡顿这才有人跑来问我Dijkstra 和 Floyd 到底该怎么选。说实话这两个名字在技术群里被问了无数次但真要在工程里给出一个让自己满意的答案远不是背个模板那么简单。这篇就以最短路算法里最容易碰到的这两块内容为主线把原理、实现、选型、坑点串一遍。适合正在学图论的初学者也适合准备算法面试或者正在写路径规划 Demo 的开发者。1. 先搞清楚两个算法各自适合什么场景1.1 给最短路问题划定一个明确边界在聊算法之前先把问题本身说清楚。给定一张有向图图里有节点和带权边权重表示从一个节点走到另一个节点的代价最短路问题就是找一条从起点到终点、边权之和最小的路径。工程里最常见的两种变形是单源最短路也就是给定一个起点求它到所有其他点的最短距离另一种是全源最短路要求图中任意两点之间的最短距离和对应路径。这里有一个关键前提必须分清楚讨论 Dijkstra 时默认所有边权都是非负数因为这是 Dijkstra 贪心策略成立的核心条件。Floyd 则稍微宽松一些能处理没有负环的负权边。所谓负环就是图中存在一个环绕一圈的总权重还是负数这种情况下最短路径没有下界任何算法都无法给出有限的答案。先约定记号n 表示节点数m 表示边数。Dijkstra 的堆优化复杂度通常写成 O((nm)log n)Floyd 的复杂度则是稳定的 O(n^3)。也就是说当 n 大到几百几千时Floyd 和 Dijkstra 的差距会呈现数量级的差别后面会专门用实例说明。1.2 Dijkstra 为什么快贪心锁点的逻辑Dijkstra 的核心思路可以概括成一句话每次从未确定的点里挑一个当前距离最小的点把它“锁死”然后用它去更新相邻点。为什么敢“锁死”我们用一个生活化的比喻来解释。假设你站在起点每个点的当前距离就是“已知的到该点最短试探距离”。既然所有边权非负那么从起点出发任何一条绕路到达当前最小距离点 u 的路径都必须先经过某个距离不小于 u 的点绕路本身只会让路径更长。因此当前距离最小的点 u不可能再通过其他点绕出一条更短的路径它此刻的距离就是真正的最终答案。这就是贪心算法的典型特征局部最优的选择能导出全局最优。Dijkstra 每次选择当前距离最小的未访问点并永久标记它这个过程不断重复直到所有可达点都被锁定。朴素实现的寻找最小点需要 O(n) 扫描整个算法为 O(n^2)使用优先队列后寻找最小点的时间降为 O(log n)总复杂度变为 O((nm)log n)。后面的完整实现部分会给出代码但先记住这个“锁点”直觉调试时遇到问题会更容易定位。1.3 Floyd 为什么简单三维 DP 的降维思维Floyd 的代码量很少通常十几行就能写完但网上关于“k 为什么必须写在外层”的问题层出不穷。理解了它的原理这些问题就不存在了。Floyd 本质上是一个动态规划过程。定义 f[k][i][j] 表示“只允许使用编号小于等于 k 的节点作为中间节点时i 到 j 的最短距离”。动态规划转移方程是f[k][i][j] min( f[k-1][i][j], f[k-1][i][k] f[k-1][k][j] )含义很直接从 i 到 j要么不经过新加入的节点 k路径还走原来的老路要么经过 k那就从 i 先到 k再从 k 到 j。因为 k 的加入是逐步扩大的这个转移天然保证了完整性。实际写代码时k 这一维可以滚动掉二维矩阵直接原地更新于是变成d[i][j] min(d[i][j], d[i][k] d[k][j])这也解释了为什么 k 必须放在最外层。如果 k 放在内层就相当于在某一个 i、j 的循环体内部同时使用不同“层级”的 k 值状态的先后顺序被打乱结果必然错误。Floyd 能处理负权边是因为每一轮 k 的迭代都是一次全局修正负权边带来的影响会在后续轮次被矫正。但一旦存在负环每绕一圈距离更小最短路就没有了有限答案。1.4 一张表做出工程选型实际项目里很少有人会把所有最短路算法都实现一遍通常是先根据场景筛选。我把常见场景整理成下面这张表场景边权条件推荐算法复杂度单源最短路非负权Dijkstra 堆优化O((nm)log n)单源最短路存在负权但无负环Bellman-Ford 或 SPFAO(nm)SPFA 平均更好全源最短路n 较小几百以内FloydO(n^3)全源最短路n 较大、图稀疏跑 n 次 DijkstraO(n(nm)log n)全源最短路存在负权Johnson 算法O(nm n(nm)log n)看到这张表很多读者会问全源最短路为什么不用 Floyd 一把梭答案是当 n 超过 500 或 1000 时n^3 的增长非常夸张。假设 n1000Floyd 要做十亿次级别的松弛操作而如果图稀疏、m 只有几千跑 n 次堆优化的 Dijkstra 只要几百万次操作差距是两个数量级以上。反过来如果 n 很小比如几十Floyd 写起来最省事还天然记录了所有点对距离工程上非常舒服。2. 手写 Dijkstra从朴素到堆优化每一步都不白走2.1 数据结构先定好邻接表怎么选Dijkstra 的实现细节里图的存储方式是第一步。邻接矩阵的优点是随机访问任意两点的边权是 O(1)但空间是 O(n^2)。n 一旦到 10 万邻接矩阵直接爆内存就算 n 只有几千在很多内存受限的场景也不划算。邻接表只存实际存在的边空间 O(nm)对堆优化版本来说更重要我们每次从堆顶弹出节点 u需要快速遍历 u 的所有出边邻接表天然支持这种操作。工程上我习惯用数组 结构体的方式或者直接用 vector 存边python 场景则用 list of dict。C 里常用这样一段struct Edge { int to; int w; }; vectorEdge graph[MAXN];存无向图的时候每条边要加入两次有向图只需要一次。输入数据如果可能给出重边要保留最小的那条因为多条同向边叠加后只有权重最小的对最短路有贡献。2.2 朴素 Dijkstra 完整实现先给出朴素的 O(n^2) 版本。它代码简单、不容易写错在稠密图里甚至常常比堆优化更快因为稠密图里堆的 log n 常数也不容忽视。const int MAXN 1005; const int INF 0x3f3f3f3f; int dist[MAXN]; bool used[MAXN]; vectorEdge graph[MAXN]; void dijkstra_naive(int s, int n) { fill(dist, dist n 1, INF); memset(used, 0, sizeof(used)); dist[s] 0; for (int i 1; i n; i) { int u -1; int best INF; // 找当前距离最小的未访问点 for (int v 1; v n; v) { if (!used[v] dist[v] best) { best dist[v]; u v; } } if (u -1) break; // 剩下的点都不可达 used[u] true; // 用 u 松弛邻居 for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; } } } }这里的 used 数组就是前文说的“锁点”。每次找最小点时扫描全部节点所以复杂度是 O(n^2)。注意初始化时 i 从 1 到 n节点编号按 1 开始如果节点从 0 开始相应地改成 0 到 n-1。提示如果图是稠密图n 只有几百几千且 m 接近 n^2朴素版往往比堆优化版还快。因为堆优化的常数开销在这种规模下可能超过 O(n^2) 的扫描成本。很多算法模板只教堆优化容易让人误以为朴素版没意义其实它非常适合稠密小图。2.3 优先队列优化版本当 n 在 10 万级别、图又稀疏的时候朴素版每一次扫描都是灾难必须用堆来维护当前距离最小的点。C 的 priority_queue 默认是大顶堆所以要用 pair 或者自定义比较器。常见写法是把距离的相反数放进去或者用 greater 指定小顶堆。下面是完整模板const int MAXN 100005; const int INF 0x3f3f3f3f; vectorEdge graph[MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra_heap(int s, int n) { fill(dist, dist n 1, INF); memset(vis, 0, sizeof(vis)); dist[s] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 跳过已经确定最短路的点 if (vis[u]) continue; vis[u] true; // 如果不用 vis也可以用 if (d ! dist[u]) continue; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } }先解释 pair 的排序逻辑。priority_queue 默认按 pair 的第一个元素排序first 是距离所以堆顶总是距离最小的那个。greater 只是把默认的大顶堆翻转成小顶堆。节点一旦被更新我们就把新的距离和节点编号再次 push 进堆因此堆里可能存在同一个节点的多个旧条目。每次弹出时通过 vis 判断这个节点是否已经确定了最终最短路是则跳过。这个“跳过旧条目”是关键细节下面专门展开。为什么 vis[u] continue 不会导致漏更新因为当 u 第一次以当前最短距离从堆顶弹出时贪心性质保证它已经不可能再被其他点更新后续所有相同节点的条目都是冗余的。所以先弹出先锁定后面重复弹出直接忽略。如果写成 if (d ! dist[u]) continue效果一样因为 d 不是最新距离说明这条记录已经过期。从复杂度角度看每条边最多触发一次成功的松弛每次成功松弛都会向堆里 push 一次堆至多 O(m) 条记录每次 pop 是 O(log m)总复杂度 O((nm)log n)。2.4 顺手把最短路径也打出来实际项目中不能只返回距离很多场景需要路径本身。Dijkstra 记录路径的思路很简单更新 dist[e.to] 时把 prev[e.to] 设置为 u。最终从终点反向追溯 prev 就能得到路径。打印时用一个栈或者递归逆序输出。示例代码如下int prev_node[MAXN]; void dijkstra_with_path(int s, int n) { // dist, vis 初始化同上 memset(prev_node, 0, sizeof(prev_node)); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; prev_node[e.to] u; pq.push({dist[e.to], e.to}); } } } } void print_path(int s, int t) { if (dist[t] INF) { cout 不可达 endl; return; } vectorint path; for (int v t; v ! 0; v prev_node[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int i 0; i path.size(); i) { if (i) cout - ; cout path[i]; } cout endl; }注意 prev 数组初始化为 0表示没有前驱。起点 s 的 prev 保持 0所以回溯到 0 时停止。这个方法对路径记录要求不高的小图完全够用。3. Floyd 十行代码背后的几个坑3.1 k 必须在外层很多人栽在这里Floyd 的代码极简单写错了也不容易一眼发现因为它们不会直接报错而是给出一个偏大的错误结果。最典型的问题就是三重循环的嵌套顺序。正确顺序是 k 在外层i 和 j 在内层。前面讲原理时说过k 每一轮代表“允许使用新加入的节点作为中间节点”这个顺序是状态转移过程的核心。如果写反了比如把 k 放在最内层那么对于一对 i、j会在同一个 i、j 循环里连续尝试所有 k。这种做法完全没有状态累计当你第一次尝试 k1 时还没更新任何结果下一次尝试 k2 时也没有把 k1 的结果纳入进去。最终 bug 的表现通常是距离没更新够路径明显绕远或者在某些不可达的节点之间给出了不合理的值。我见过最有效的检查方法是用三重循环顺序的三层含义来帮助记忆最外层 k 代表“决策中间节点的编号上限”内层 i、j 则是在这个限制背景下枚举所有起点和终点。直接背 i、j、k 的顺序容易错背语义就不会踩坑。3.2 顺手把路径也记录下来Floyd 的路径重建比 Dijkstra 稍微绕一点。常见的办法是开一个 next[i][j] 数组表示从 i 到 j 的最短路径上i 的下一个节点是谁。初始化时对于每一条有向边 i-jnext[i][j] j没有边的则默认保持 j 或 0。在松弛成功时更新 nextif (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; next[i][j] next[i][k]; }这里如果想当然写成 next[i][j] k就错了。因为 i 到 k 的最短路径可能已经经过了其他中间节点i 走向这个新路径上的第一个节点不一定是 k而是 next[i][k]。只有记录 next[i][k]才能完整还原路径。打印路径时只需要从 next[i][j] 出发不断跳转void print_floyd_path(int u, int v) { if (d[u][v] INF) { printf(不可达\n); return; } printf(%d, u); while (u ! v) { u next[u][v]; printf( - %d, u); } printf(\n); }3.3 初始化、重边、自环三个习惯一次养成Floyd 的初始化往往决定成败。首先把整个矩阵 d[i][j] 初始化为 INF再把 d[i][i] 初始化为 0。接下来读入边。输入如果出现重边要取最小值自环即 i 到 i 的边在非负权场景下不会对最短路有正面贡献可以忽略但如果存在负权自环那就相当于负环问题整个最短路都不成立通常需要单独排查。INF 的选择也要小心。很多人直接用 int 的 INT_MAX然后判断 d[i][k] d[k][j] d[i][j]一旦 d[i][k] 和 d[k][j] 都是 INF两者相加直接溢出变成负数导致错误更新。我在工程里习惯用 0x3f3f3f3f这个值约等于十亿两个相加也不会溢出 32 位 int同时还能继续满足“比任何真实路径都大”的需求。更好的习惯是松弛时显式判断if (d[i][k] ! INF d[k][j] ! INF) { if (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; } }这样写虽然多两行但能避免所有溢出的心智负担。数据范围较大、边权可能达到 10^9 时把 dist 数组的类型改成 long long判断逻辑不变。4. 真实案例复盘一个导览项目里的最短路选型4.1 一个再常见不过的场景前文提到的园区导览项目最初的模型很简单几十个展览点位作为图节点点与点之间的步行路线作为边游客想去任意两个点位之间系统需要给出最短步行路线和距离。当时节点少Floyd 一次预计算全部点对之后再查询都是 O(1) 查表完全没问题。后来团队把监控点位、商店、洗手间等大量新节点都并入了同一张图节点数从 30 涨到 700 多边数接近 2000图仍然很稀疏。Floyd 的预计算开始变成瓶颈在纯 Python 的调试脚本里700^3 大约三亿多次操作肉眼可见地卡顿。更重要的是后续还希望支持动态修改某些边权每次修改如果都重跑全源 Floyd体验会非常差。这个时候真正需要权衡的问题就变成了查询频率高不高图会不会频繁更新如果只是偶尔算一次全量数据Floyd 其实也能接受但如果是频繁的单点查询并且图规模不小Dijkstra 明显是更稳的选择。4.2 性能对比与实测印象为了说清楚这个问题我在项目里用随机生成的 600 个节点、1800 条边的稀疏图做过一个简单对比。理论复杂度如下算法复杂度n600, m1800预估操作规模朴素 Dijkstra 单源O(n^2m)约 36 万次堆优化 Dijkstra 单源O((nm)log n)约 1.6 万次Floyd 全源O(n^3)约 2.16 亿次可以看到单源 Dijkstra 和全源 Floyd 差了好几个数量级。实际跑起来C 编译优化后的结果更明显堆优化 Dijkstra 完成一次单源计算在毫秒级Floyd 跑完全源需要零点几秒而纯 Python 的三重循环要慢得多交互式查询时卡顿感非常强。所以最终核心模块用 C 重写每个游客查询时按需跑一次 Dijkstra只计算需要的那个终点路径返回也顺手。这里有个工程心得如果系统需要频繁查询“任意两点”且图节点少于 200Floyd 的预计算模式非常舒服查询 O(1)代码简单一旦节点上了 500就要认真考虑改成“每次查询跑 Dijkstra”或者“按热点区域做预计算”。选型不是背复杂度公式而是理解自己系统中的查询比例和更新频率。4.3 落地时的几个代码细节实际落地时除了算法本身还要处理几个工程细节。第一图的存储从邻接矩阵换成了邻接表因为 700 个节点的邻接矩阵是 49 万格虽然内存上不算大但遍历出边时邻接表快得多。第二输出路径时统一封装成接口前端只拿节点序列和总距离不关心内部是 Dijkstra 还是查表方便日后替换。第三因为图数据来自多个信息源重边几乎必然存在读入阶段统一取最小值否则 Dijkstra 会被无关重边干扰。这里还要提醒一点最短路算法只是路径服务的一环真实系统里往往还涉及禁行路段、步行耗时估计、逗留时长等业务规则。我习惯在算法层之上做一层“路网服务”把最短路计算和业务规则解耦这样算法升级或替换时上层完全不用改。5. 常见问题与排查技巧实录5.1 队列里全是旧数据你被坑过一次就懂了堆优化 Dijkstra 最常见的问题就是忘记处理堆里的“过期数据”。现象是某些节点的 dist 偏大或偏小程序在随机数据上偶尔正确一旦图复杂一点就全乱。原因很多新手分析不出来。事实上每次 dist[e.to] 被更新时我们都会往堆里 push 一个全新的 pair同一个节点可能在堆里同时存在多个不同距离的记录。如果不对过期记录做任何判断程序就可能把一条已经过期的旧距离当成当前距离来松弛邻居。举例来说某个节点先被一条较长的路径更新入堆后来又发现更短的路径再入堆。堆顶弹出的应该是更短的那条但如果代码没有跳过旧记录它可能用旧距离继续更新邻居算出来的结果就不是最优。修复方式就是前面代码中的 vis 标记或 if (d ! dist[u]) continue。从工程角度写 Dijkstra 时最好一开始就把跳过过期记录的代码写进去。这行代码不是可选项而是正确性的必要条件。5.2 负数权边的反直觉案例有一个经典反例可以瞬间击碎对 Dijkstra 的盲目信任。假设起点是 s存在 s-a 边权 5s-b 边权 6b-a 边权 -2。直观上s 到 a 的最短距离是走 s-b-a路程 4但 Dijkstra 一开始会选择从 s 出发距离更小的 a直接锁定 5然后才处理 b。最终它输出的 s 到 a 的距离是 5而正确答案是 4。原因在于 Dijkstra 锁点依赖的是“绕路不会更短”的性质而负权边彻底破坏了这一点绕路虽然经过更远的点但负权可能把总代价拉回更低。所以只要输入里有负权边Dijkstra 就必须彻底换掉改用 Bellman-Ford 或 SPFA。Floyd 可以处理单个负权边但对负环无能为力。遇到负权先想想问题本身是否合法再进行算法选型。5.3 越界与溢出的隐蔽 Bug最短路代码里最隐蔽的错误不是逻辑混乱而是 INF 加法溢出。当 INF 取 INT_MAX且两个不可达节点的距离相加时结果溢出成负数程序反而认为它是一条更短路径。这种事在 Floyd 的朴素写法和 Dijkstra 的比较条件里都可能出现。我推荐的防御姿势有两个。第一个是 INF 用 0x3f3f3f3f保证 INF INF 不溢出第二个是写比较时拆开判断像前面 Floyd 初始化那节写的一样先判断不等于 INF再做相加比较。如果数据范围很大干脆把 dist 数组声明为 long long用 long long 的 INF比如 4e18彻底告别整数溢出问题。很多比赛选手习惯性地开 long long不是没有道理的。5.4 怎么快速验证算法写对了写完之后怎么确认实现正确单靠眼睛看代码通常不够。我最常用的方法是构造小图手算。找一个五六个节点的样例把 dist 数组按轮次手推一遍跟程序输出对比。这个过程不麻烦但能快速暴露初始化、循环顺序、路径输出等细节问题。第二个方法是对拍。边权全部设为 1 的图Dijkstra 的结果应该和 BFS 的层数完全一致用这段代码对比很快。更通用的对拍是用 Floyd 验证 Dijkstra随机生成一张小图跑一遍 Dijkstra 得到单源最短路再跑一遍 Floyd 得到全源最短路比较特定起点的所有 dist 是否一致。如果两者对不上说明其中某个实现有问题。由于 Floyd 结构简单通常默认它是基准。这个“暴力对拍”的思路在工程里也常用把新实现和线上基准跑同一批数据用脚本自动比对输出能省下大量排查时间。6. 用不上的时候也要知道进阶方向6.1 有负权边的全源场景如果一张图既有负权边又需要全源最短路直接跑 n 次 Dijkstra 是不行的因为 Dijkstra 根本不能处理负权。这时候可以了解一下 Johnson 算法它的思路非常经典先跑一遍 Bellman-Ford 给每个节点算一个“势能”然后用势能重新调整所有边的权重把所有边权变成非负数最后再跑 n 次 Dijkstra。调整权重的方式是对于每条边 u-v把实际权重变成 w h[u] - h[v]。这个变换的好处是最短路径不会因为变换而改变因为路径上的势能项会前后抵消。工程中很少需要自己实现 Johnson但理解它有助于建立完整的算法知识体系。面试中如果被问到“负权全源怎么处理”能说出 Johnson 的思路是很加分的。6.2 比 Dijkstra 更快带上启发式在路径规划场景中Dijkstra 在一个很大的图上找单个目标点时会把图里大量无关区域都扩展一遍。这个时候可以用 A* 算法它在 Dijkstra 的基础上增加一个启发式估计 h(n)表示从当前节点 n 到目标点的估算代价。只要 h(n) 不过度估计真实代价A* 就保证找到最优路径而且扩展的节点数通常远小于 Dijkstra。Dijkstra 相当于 h(n)0 的特例所以从 Dijkstra 迁移到 A* 的代码成本非常低主要改动只是把优先队列里的排序键从当前距离变成当前距离加启发值。地图导航、游戏寻路里最常见的做法就是 A* 配合栅格地图这也是最短路算法的经典应用延伸。如果做的是实时路径规划A* 往往比单纯堆优化的 Dijkstra 实用得多。6.3 当图变成了动态图真实系统中几乎没有永远静态的边权。路况变化、场地临时封闭、某个节点暂停开放都会让之前的计算结果失效。最直接的做法是重新跑一遍算法但如果图很大而且更新频繁重复计算成本太高。这个方向上的常见策略包括局部更新、增量维护、或者把图拆成区域预处理。最短路动态更新的核心困难在于一条边变化可能影响很多节点但通常影响范围是局部的。工程上的一个简单思路是先用旧结果判断受影响的节点范围再在局部重跑 Dijkstra。很多商业导航系统背后都有类似的增量计算逻辑但实现复杂度明显高于静态算法。日常开发中如果遇到动态图不要急着写复杂的增量逻辑先评估更新频率很多时候“重新跑一次”反而是最简单也最稳定的方案。我个人在实际项目里的体会是最短路算法看起来是图论里的基础题但真正用好的关键是知道每个算法的前提条件、复杂度数量级和最容易被忽视的细节。Dijkstra 的贪心锁点、Floyd 的三层递推都值得亲手写一遍、亲手掉一次坑。如果你正在学习这块我建议从一张六节点的小图开始手动推一遍 dist 数组再用代码跑一遍最后把打印出来的路径逐条读一次。这个过程比背十个模板都有用。
阅读完成 · 觉得有帮助？
