先聊点实在的。只要你在大学认真上过《数据结构》或者《算法设计与分析》Dijkstra和Floyd这两个名字绝对是绕不过去的。我当年学的时候也觉得它们就是两个“背模板”的算法直到后来真的在项目里做路径规划、做地图导航的数据预处理时才意识到这两个算法背后的取舍、适用边界和性能差异才是真正值得掰开揉碎搞清楚的东西。这篇不聊那种“定义-步骤-复杂度”的教科书复述我直接把我实际敲代码、调性能、踩坑的经验拿出来讲。这篇内容适合正在准备面试的在校生、刚入职被分到地图或网络相关模块的工程师以及任何想真正搞懂“多源最短路径”和“单源最短路径”为什么不能瞎换着用的人。你只要会最基本的数组、队列和一点点动态规划思想就能完全看懂。1. 内容整体设计与思路拆解1.1 最短路径问题的本质是什么先说清楚我们在解决什么问题。给定一张带权图也就是一堆节点和一堆带数字的边最短路径问题问的是从某个点走到另一个点怎么走能让路径上所有边的权值加起来最小。这里有个特别容易混淆的点边的权值不一定代表“长度”。它可以代表时间、金钱成本、换乘次数甚至是你自己定义的代价。我在一个物流调度项目里就把边的权值定义成了“途经该路段的预计拥堵时长”算法本身完全不关心权值代表什么它只负责把总和算到最小。这也是图论算法最值钱的地方——模型搭好算法通用。最短路径问题本身还分好几类。单源最短路径是指“从固定一个点出发到其他所有点的最短路径”多源最短路径是指“任意两个点之间的最短路径”。Dijkstra解决的就是前者而且是所有单源算法里最经典的一个Floyd解决的是后者虽然它在数据集稍微大一点时性能就崩但它在点少、边多、要全量计算的场景里仍然无可替代。1.2 为什么偏偏是Dijkstra和Floyd算法那么多为什么流传最广的是这两个我的理解是它们恰好站在两个极端。Dijkstra是一个基于贪心策略的“增量扩散”过程思路像水波纹从落点往外扩散Floyd则是一个基于动态规划的“全方位枚举松弛”过程思路像把所有点都拉到一个矩阵里反复比对整理。一个适合找“单人最短路径”一个适合找“全员最短路径”两者结合基本覆盖了最常见的两类需求。而且这两个算法的思维模式非常经典Dijkstra把“选最小值”和“更新邻居”两个操作抽象出来这是很多更复杂算法比如A*寻路、网络路由协议的原型Floyd则把“中间点中转”这件事讲透了理解了它你就理解了动态规划为什么能把三维状态压缩成二维矩阵。所以不管从面试角度还是从实际工程角度它们都是性价比最高的两个算法。我在实际项目里也试过用SPFABellman-Ford的队列优化版和Johnson算法适用于稀疏图的“先重赋权再跑Dijkstra”但坦白说日常遇到的90%场景都跑不出Dijkstra的手掌心。Floyd看着笨但它在点数量级小于几百的时候代码简单到不可能写错这本身在工期紧张时就是巨大的优势。1.3 两个算法选型的核心差异一句话概括选型思路如果只需要从一个源点出发查最短路径且图中没有负权边无脑用Dijkstra如果直接需要图上所有点对之间的最短距离而且节点数在几百这个量级Floyd是简单粗暴的最优选。这不是随便说的。时间复杂度是两个算法最直观的分水岭Dijkstra用普通数组实现是O(V²)用优先队列优化后是O((VE)logV)Floyd固定是O(V³)。当V从100涨到1000Dijkstra的运算量涨到约100万级别用堆优化后更低Floyd则直接冲到10亿级别这个差距在实际跑的时候就是“秒回”和“等半天”的区别。但反过来如果图特别稠密边数接近V²Dijkstra的O((VE)logV)反而会退化因为每条边都要执行一次邻居更新此时Floyd的简单循环在常数上往往有惊喜。这就是为什么我要在第三章给你写清楚“什么场景下选什么”而不是简单背个结论。2. 核心细节解析与实操要点2.1 Dijkstra的贪心思想为什么每次选最小的就对了Dijkstra的核心操作一句话就能说清维护一个“已经确定最短路径”的节点集合S每次从还没进集合的节点中挑一个距离起点最近的点把它放入集合然后用这个点去更新它所有邻居的距离。这个“每次挑最小”就是贪心。但你有没有想过为什么挑最小的这个操作是正确的为什么不能随便挑一个点先去更新邻居关键在于如果所有边的权值都是非负的那么当前距离起点最小的那个点它的最短路径已经被彻底确定了。你想就算之后通过其他点绕路到它绕路本身的路程至少大于等于0只会让总距离变大或相等不可能比现在的值更小。这个直觉非常重要也是Dijkstra处理不了负权边的根本原因——一旦出现负权边“绕路”反而可能让总距离变小那你凭什么说眼前的“最小”就是全局“最小”我记得当时自己写了个笔记帮助理解想象你在一个操场上手里拿着一个沙漏从起点沿不同方向跑边跑边看哪些点先被“碰到”。Dijkstra就是按每个点距离起点的真实远近依次“碰到”它们而且一旦碰到就永远不会再来一次更短的。每次从优先队列里弹出的那个最小距离就是“流水线上下一个被确定标签的点”。2.2 一个细节为什么不能用队列替代优先队列新手最容易犯的错误就是拿普通队列去模拟DijkstraBFS思维根深蒂固觉得“一层一层往外扩”就行。但在带权图里先出队的节点不一定就是当前全局距离最小的节点。举个例子起点s到邻居a的距离是100到邻居b的距离是1如果你先把a入队并“确定”了它的最短距离是100然后才处理b那等到b再更新到a时发现经过b到a只要50这时候a的最短距离已经被你锁定了你只能推翻自己。处理不好就会陷入重复入队、重复更新的泥潭。正确做法是用优先队列最小堆每次自动把当前全局距离最小的节点弹出来处理。这样才能保证每个节点出队一次时它的距离就是最终答案。这也是我建议你写Dijkstra时直接用堆优化版本的原因普通数组扫最小值的O(V²)版本在点超1000时明显感觉到卡顿。2.3 Floyd的动态规划模型三维变二维Floyd的思路其实是一个动态规划递推。定义dp[k][i][j]表示“只允许经过编号不超过k的中间节点时从i到j的最短距离”。那么有两种情况不经过节点kdp[k][i][j] dp[k-1][i][j]经过节点kdp[k][i][j] dp[k-1][i][k] dp[k-1][k][j]两者取小。妙就妙在这个三维数组可以直接压缩成二维因为我们更新dp[i][j]时用到的dp[i][k]和dp[k][j]在这个k循环里已经被更新成了“包含节点k”的版本而这恰恰就是我们需要的结果。所以三行循环就能完成这也是为什么Floyd的代码看起来短到惊人。我常常跟别人说Floyd就是“不停地让新节点当中转站”的过程。你可以想象一个班级里有20个人最开始大家只知道直接认识的同学的距离然后班长说现在每个人都可以通过小明互相认识我们把路径更新一下接下来每个人都可以通过小红互相认识再更新一下……20个人循环下来所有人之间的“最短介绍路径”就有了。2.4 负权回路的禁忌Floyd为何分辨不出Floyd可以处理负权边这是它比Dijkstra宽容的地方。但如果你给Floyd一张存在负权回路的图比如有一个环所有边权值加起来是负数那么算法只会傻傻地循环更新因为每绕一圈都能得到更小的距离永远收敛不了。实际使用中Floyd在初始化时把不直接相连的点对距离设为INF一个很大的值算法跑完后如果发现某个dist[i][i]变成了负数说明存在负权回路这时候得到的所有最短路径都是无意义的。我在项目里遇到过一次类似情况排查了很久才发现是原始数据里有一条负数重复边没有被清洗掉所以如果你在工程里用Floyd处理带有外部输入权值的数据一定要先做数据校验或者在算法结束后加一个对角检查。3. 实操过程与核心环节实现3.1 邻接矩阵还是邻接表面对数据先做出选择在动手写代码之前第一个要做的决定就是用什么数据结构存图。这个选择直接影响空间复杂度和代码复杂度。邻接矩阵二维数组matrix[i][j]表示从i到j的直接距离。好处是查询两个点之间的距离是O(1)Floyd天然依赖这种数据结构坏处是空间占用O(V²)V到5000时光存的就不太现实了。邻接表每个点维护一个列表存它能到的邻居和边权。好处是只存储真实存在的边空间O(VE)坏处是查询两点是否相邻没有矩阵那么快但对单个点的邻居遍历非常友好。实际工程中如果V在1000以下且图比较稠密我倾向于直接用邻接矩阵因为代码可读性和调试难度都比邻接表低很多。Dijkstra用邻接表配合优先队列是教科书标配Floyd则几乎只搭配邻接矩阵。下面两个章节我会分别把这两套写法都贴出来。3.2 Dijkstra标准模板堆优化版我平时用的最多的就是堆优化版Dijkstra它比普通版代码长不了几行但性能完全不在一个档次。这里我直接用C写一个最清晰的版本完全按照工程习惯来读入部分省略只展示核心逻辑。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 100010; struct Edge { int to, weight; }; vectorEdge graph[MAXN]; int dist[MAXN]; bool visited[MAXN]; void dijkstra(int start, int n) { // 初始化距离数组 for (int i 1; i n; i) { dist[i] INF; visited[i] false; } dist[start] 0; // 优先队列pair距离, 节点编号 // 这里用greater保证最小值先出队 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 如果这个点之前被处理过且当前出队的距离比记录还大跳过 if (visited[u]) continue; visited[u] true; // 遍历邻居 for (const Edge e : graph[u]) { int v e.to; int w e.weight; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这段代码有两个关键细节值得专门提一下。第一为什么需要visited数组因为同一个节点可能被多个不同的路径同时压入优先队列如果不加visited判断弹出旧值时还会再跑一遍邻居更新虽然不影响正确性但是白白浪费性能。加上visited标记后每个节点最多出队一次复杂度才有保证。第二为什么初始化用0x3f3f3f3f而不是INT_MAX因为INT_MAX加上一个正数会溢出变成负数这在比较大小的时候会产生极其隐蔽的bug而0x3f3f3f3f大约是10亿再加上一个边权也不会溢出而且两个0x3f3f3f3f相加也不超出int范围。这个细节在比赛和工程里都非常实用。如果你要用Python实现核心逻辑完全一样只是把优先队列换成heapqimport heapq def dijkstra(graph, start, n): INF float(inf) dist [INF] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return distPython版本里面if d dist[u]就是前面C里visited数组的作用。这种“惰性删除”的写法更简洁但节点数量大的时候队列里可能会积累很多过期条目内存占用会稍高。对绝大部分业务场景来说完全没问题。3.3 Floyd标准模板三行循环的优雅与陷阱Floyd的代码可以说是“短小精悍”四个字的代言人。我直接把完整可跑的C代码放出来然后逐行解释每层循环在干什么。#include bits/stdc.h using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; int dist[MAXN][MAXN]; int n, m; void floyd() { // k是中间节点 for (int k 1; k n; k) { for (int i 1; i n; i) { if (dist[i][k] INF) continue; // 剪枝i到k不可达就跳过 for (int j 1; j n; j) { if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } } int main() { cin n m; memset(dist, 0x3f, sizeof(dist)); for (int i 1; i n; i) { dist[i][i] 0; // 自己到自己的距离是0 } for (int i 0; i m; i) { int u, v, w; cin u v w; dist[u][v] min(dist[u][v], w); // 防止有重复边取最小 } floyd(); // 输出所有点对最短距离 for (int i 1; i n; i) { for (int j 1; j n; j) { if (dist[i][j] INF) cout INF ; else cout dist[i][j] ; } cout endl; } return 0; }很多初学者会在看这段代码时问一个问题为什么k循环要放在最外层能不能把k放在内层这个问题问得特别好答案其实跟动态规划的状态转移顺序有关。Floyd的递推公式要求的是“在只允许经过前k个节点的情况下更新dist[i][j]”如果k放在最内层那么在计算dist[i][j]时dist[i][k]和dist[k][j]可能已经经过了比k更大的中间节点这就违反了状态的定义算出来的结果就是错的。我当年自己写错一次后专门用一个小图人肉跑了几个来回才真正感受到“最外层枚举中转点”这个顺序是Floyd的灵魂。这个顺序不是随便定的而是由DP状态转移方向决定的。所以说代码短不代表容易理解三行循环里藏的数学原理比看起来深得多。3.4 数据规模与时间预估跑步之前先知道跑多久很多人拿到一个算法题或者需求连数据规模都没看就开写结果写完了才发现时间复杂度根本扛不住。这里我给你一个直接可用的估算方法。假设你的机器每秒能执行大约10^8次简单运算这是比较常见的水平实际因CPU、语言、优化级别而异那么Dijkstra堆优化版处理V10000、E100000的图大约要执行(VE)logV约110万次操作理论上毫秒级完成。Floyd处理V500的图需要执行1.25亿次操作大约1秒左右还可以接受。Floyd处理V1000的图需要执行10亿次操作可能就要等10秒以上业务上基本不可接受。所以我的经验法则是如果节点数超过500而且你确实需要全源最短路径先停下来想一想能不能用“对每个点跑一次Dijkstra”来替代因为堆优化Dijkstra跑V次的复杂度是O(V(VE)logV)在稀疏图里往往比Floyd快得多。这其实就是Johnson算法的思想雏形在稀疏图上不要浪费O(V³)的Floyd而是想办法把负权边处理后使用多次Dijkstra。虽然Johnson的核心步骤是重赋权但选型逻辑和这个是一脉相承的。3.5 记录路径从“距离”到“完整路线”只说距离不说怎么走在很多场景下就是耍流氓。比如导航软件告诉你从A到B要30分钟但不告诉你走哪条路你会觉得这个软件难用无比。所以实际工程里几乎总会需要额外存储路径信息。Dijkstra记录路径的方法非常简单增加一个pre数组pre[v]表示在最短路径中到达v之前的那个节点是谁。在更新dist[v]时把pre[v]同步更新为u。等算法全部结束后从终点往前反推就能得到完整路径。Floyd记录路径稍微复杂一点。因为Floyd是多源的你不能简单用一个一维pre数组而是需要一个二维的path矩阵。path[i][j]表示从i到j的最短路径中j的前一个节点是谁也有一种写法是存i的后一个节点。在算法更新dist[i][j]时同步更新path[i][j] path[k][j]。最终输出路径时从终点往前递归或迭代即可。我贴一个Floyd路径记录的极简C核心代码片段int path[MAXN][MAXN]; // path[i][j] 表示从i到j的最短路径中j的前驱 void floyd_with_path() { // 初始化path for (int i 1; i n; i) { for (int j 1; j n; j) { if (dist[i][j] ! INF i ! j) { path[i][j] i; // 初始认为i直接到j } } } for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { 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]; } } } } } void print_path(int u, int v) { if (u v) { cout u; return; } print_path(u, path[u][v]); cout - v; }这里的核心逻辑是如果发现从i到j的最短路需要经过k那么j的前驱就应该变成“从k到j的最短路中j的前驱”也就是path[k][j]。递归打印时自然就能把整条路径串联起来。4. 常见问题与排查技巧实录4.1 为什么Dijkstra不能处理负权边这是面试官最喜欢问的一个问题也是实际场景里最容易翻车的一个点。负权边指的是边的权值小于0比如“这段路走完反而能获得收益”。Dijkstra的贪心正确性建立在“所有边权非负”这个前提下。一旦出现负权边之前说的“当前最小距离一定是最短路径”就被推翻了因为可能有一个距离很大的点通过一条负权边绕回来“抵消”掉前面的路长反而变成最短路径。举个例子你就明白了起点s到a的距离是5s到b的距离是10a到b的距离是-8。那么从s经过a再到b总距离是5(-8)-3这比直接从s到b的10要短。但Dijkstra在第一步就会发现dist[a]5最小先把a标记为已确定然后更新b的距离变为-3。看起来没问题问题是如果边的结构更复杂一点比如还有一个点cdist[c]6而且c到b有一条-4的边Dijkstra在第二步会认为c比b现在是-3大从而先处理c再处理b但真实的最短路径可能是s-c-b2比s-a-b-3要大所以不影响结果。可如果负值出现在更隐蔽的位置贪心就会出错。我推荐的做法是如果业务数据里明确可能出现负权直接用Bellman-Ford或SPFA别跟Dijkstra死磕。4.2 INF怎么设置才不会被溢出坑到这个坑非常隐蔽我亲眼见过不少新手在这里翻车。你设定INF为INT_MAX然后判断dist[i][k] dist[k][j] dist[i][j]时两个INT_MAX直接相加结果是未定义行为在C里就是溢出变成了一个负数然后这个负数被当成“更短路径”写进dist数组整个计算结果直接崩掉。解决办法有三种使用long long类型存距离INF设置为0x3f3f3f3f3f3f3f3f这样的64位大数这样相加也不溢出。使用long long类型存距离INF LLONG_MAX / 4保证至少两个INF相加不会溢出。在更新前判断dist[i][k] INF或dist[k][j] INF有一方不可达就直接跳过不进行相加操作。在实际工程里我习惯两种方式同时用一方面把INF设置成一个大数一方面在相加前做不可达判断。因为哪怕用了大数INF如果边权本身也很大比如十亿级别两个加一起还是会溢出。所以在Floyd的内层循环里先判断再相加是个好习惯。4.3 有向图和无向图初始化时的细节分歧无向图的特点是边是双向的你输入一条u到v权值为w的边实际上要在邻接矩阵里同时设置dist[u][v] w和dist[v][u] w。邻接表里也一样要在u的链表里加v也要在v的链表里加u。有向图就只加一条。这个看似简单但在多源数据导入时特别容易出错。我之前处理过一个道路网络数据源文件里提供的路段信息是单向的我忘了反转导致大量路径无法反查排查了一下午才发现是初始化阶段漏了对称赋值。建议用一个辅助函数处理图的构建比如add_edge(u, v, w)内部根据图类型决定是否双向添加。这样至少从代码层面降低了一个低级错误的概率。4.4 重建路径时的递归深度陷阱路径记录后如果你用递归来打印路径图特别长比如几百个点串成一条线递归深度可能会非常大甚至导致栈溢出。我不止一次见到有人在算法都正确的情况下卡在路径输出这一步APP直接崩溃。解决办法有两个一是把递归打印改成迭代用一个vector把路径节点收集起来然后反转输出二是把系统栈空间调大。但根本解法还是推荐迭代void print_path_iterative(int u, int v) { vectorint path_nodes; int cur v; while (cur ! u) { path_nodes.push_back(cur); cur path[u][cur]; } path_nodes.push_back(u); reverse(path_nodes.begin(), path_nodes.end()); for (int i 0; i path_nodes.size(); i) { if (i 0) cout - ; cout path_nodes[i]; } cout endl; }这段代码先把终点往前一个个推回起点再把整个向量反转就是一个正序的完整路径。整个过程是迭代的不存在栈溢出风险。4.5 从邻接矩阵迁移到邻接表需要注意的差异很多人刚接触堆优化Dijkstra时喜欢先把邻接矩阵写好再转邻接表。这里有一个常见的逻辑差异邻接矩阵天然会保存重边同一对点之间多条边中权值较小的那个前提是你初始化时做了min处理而邻接表如果不做处理会把所有重边都存下来遍历邻居时就会多算几次无效更新。性能影响不大但逻辑上有一个副作用如果你用邻接表却在更新dist时没有判断“是不是同一条边被更新了多次”代码依然正确只是多了些无用功。最稳妥的写法是在建表时对每一条边都手动做一次“如果已有更短的边就跳过不重复添加”。不过说实话重边场景在算法竞赛里经常出现真实业务数据里反而没那么常见但写代码时多留一手总不会错。5. 实际应用场景与扩展思路5.1 导航与地图服务地图导航是最典型的最短路径应用场景。你输入起点和终点导航软件背后跑的就是Dijkstra的变体——A算法。A相比Dijkstra多了一个启发式函数可以更聪明地优先扩展“看起来离终点更近”的方向能大幅减少搜索范围但核心的“维护一个已确定节点集合、不断更新邻居距离”这个骨架依然是Dijkstra的底子。如果是网约车平台的全局调度可能需要计算多个司机到多个乘客的距离这时单源Dijkstra反而不够用了工程师通常会把所有候选司机当成一个“超级源点”连接起来再做一次单源搜索或者直接把每次订单的距离预计算缓存这就涉及多源和离线预计算的思想。5.2 网络路由协议在计算机网络中OSPF开放最短路径优先路由协议里也有Dijkstra的身影。每个路由器都维护一张全网的拓扑图周期性地运行Dijkstra算法计算到达所有其他路由器的最短路径并据此生成路由表。这里的“最短”通常指链路代价最低而链路代价可以由带宽、时延、负载等综合决定。Floyd在网络领域的应用相对少一些因为网络拓扑的节点数量多、图比较稀疏Floyd的O(V³)完全撑不住。但有一种特殊场景在小型私有网络或者数据中心内部节点数只有几十个并且需要全矩阵路径表时Floyd依旧简单有效。5.3 游戏寻路与社交图谱在早期的一些游戏里如果地图不是特别大用Floyd预计算好所有NPC到玩家的路径然后直接查表是一种很省CPU的做法。我第一次在项目里用到Floyd就是在做一个类似“村庄地图传送”的小系统几十个关键点跑一次Floyd之后所有点对之间的路径都是O(1)查询。社交网络里的“六度分隔”理论也跟最短路径有关。如果把人当作节点把好友关系当作边那么两个人之间的最短路径长度理论上就是“几度分隔”。Facebook等平台很早就有相关研究用小世界理论结合最短路径算法来分析社交网络的连通性。5.4 算法竞赛面试中的变形题面试里最常考的不是裸的Dijkstra和Floyd而是它们的变形。比如求最短路径的条数在Dijkstra更新时增加一个count数组当dist[v]被更新为更小值时count[v] count[u]当dist[v]和dist[u]w相等时count[v] count[u]。求次短路径维护dist1和dist2两个数组当更新时把旧的最短距离降级为次短距离。求恰好经过k条边的最短路径利用矩阵快速幂结合Floyd的“min-plus”矩阵乘法思想。这些变形在思路上都是Dijkstra/Floyd的延伸你只要把基础原理吃透了这些扩展题其实一点都不难。6. 写在最后的实践经验我最后想说的是算法这东西光看永远学不会。我见过太多人把Dijkstra的代码背得滚瓜烂熟但一问他“为什么优先队列里要存pair距离,节点而不是pair节点,距离”他就卡壳了。如果你能回答清楚这个问题说明你真的理解了优先队列的比较规则和Dijkstra的更新逻辑。建议你拿到这篇内容后亲自动手做三件事第一用Dijkstra实现一个带路径输出的导航核心模块。不用真的去调API就用一个10个节点的图自己造数据跑通整个流程。第二把Floyd的k循环顺序故意调换观察输出结果如何变错。这个实验能让你一辈子记住“k必须在外层”的原因。第三试着把Dijkstra的代码改成使用邻接矩阵版本跑一遍和堆优化版本对比性能差异感受数据结构对算法复杂度的实际影响。这三件事做完你对这两个算法的理解会比看十篇博客都扎实。再分享一个我自己的小习惯写Dijkstra时我总会在更新dist后顺手打印一份调试日志包括当前弹出的节点、更新了哪些邻居、新的dist值是什么。这样一旦数据不对我一眼就能看出是哪一步出了问题。等代码稳定了再删掉调试日志。这个习惯帮我省了无数排查时间。
