1. 从一次导航绕路说起四种最短路算法到底该怎么选很多人第一次接触最短路问题是在做地图导航类项目的时候。我当年接的第一个相关需求是给一个园区内部做路径规划几十个路口、若干条单双向道路、每条路有通行时间权重要求输入起点终点后返回最快路线。当时我天真地以为最短路就是背一个Dijkstra模板结果真上手才发现单源还是多源、有没有负权边、图是稠密还是稀疏、要不要判负环这几个问题直接决定了你该用哪个算法。选错了要么结果错误要么性能拉胯到跑不动。这篇文章就把Dijkstra、Bellman-Ford、SPFA、Floyd这四个最短路算法放在一起讲透。它们不是四个可以随便替换的同义词而是各自有明确的适用边界Dijkstra解决非负权单源最短路Bellman-Ford解决带负权甚至能判负环的单源最短路SPFA是Bellman-Ford的队列优化版Floyd解决多源最短路。我会从原理、手写实现、复杂度、踩坑经验几个角度逐个拆解最后给出一张选型对照表。不管你是刚学图论的在校生还是要在工程里落地路径规划的开发者看完都能直接抄作业。需要先说明的是本文所有代码示例都是基于常见竞赛与工程实践的合理实现参数和复杂度结论来自标准图论教材的通用结论我会在关键处解释为什么这么设计而不是只丢一段代码给你。2. Dijkstra非负权图上的单源最短路首选2.1 贪心思想与为什么不能有负权边Dijkstra的核心是一个贪心策略维护一个已确定最短距离的顶点集合每次从未确定的顶点里挑出当前距离最小的那个把它标记为已确定然后用它去松弛relax它的所有邻居。所谓松弛就是判断经过当前点再到邻居是否比邻居已知的距离更短如果更短就更新。为什么这个贪心是对的关键在于非负权这个前提。当所有边权非负时当前距离最小的那个未确定顶点它的距离不可能再被其他路径缩短了——因为任何绕路都会引入额外的非负代价只会更长。这个性质保证了每次选出的点距离就是最终答案。反过来一旦存在负权边这个前提就崩了。举个经典反例A到B距离1A到C距离2C到B距离-2。按Dijkstra先确定B距离为1但实际上A→C→B的距离是0更短。贪心提前把B锁死了结果就错了。所以记住第一条铁律Dijkstra只适用于边权非负的图。2.2 朴素版与堆优化版的实现差异朴素Dijkstra用邻接矩阵存图每次找最小距离点用一层循环扫描复杂度是O(V²)V是顶点数。它适合稠密图因为稠密图边数接近V²堆优化反而因为堆操作多而没优势。堆优化版用优先队列小根堆维护待处理顶点配合邻接表存图复杂度降到O((VE)logV)E是边数。稀疏图E远小于V²用这个版本收益巨大。下面给一份堆优化版的Python实现注释里标了每个关键动作的意图import heapq def dijkstra(n, graph, start): # graph: 邻接表graph[u] [(v, w), ...] INF float(inf) dist [INF] * (n 1) dist[start] 0 pq [(0, start)] # (当前距离, 顶点) while pq: d, u heapq.heappop(pq) # 关键懒惰删除。如果堆里取出的距离已经过时直接跳过 if d dist[u]: continue for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist这里有个新手最容易忽略的点懒惰删除。因为Python的heapq不支持修改堆中已有元素我们只能往堆里重复push新距离出堆时用if d dist[u]: continue把过期的旧记录丢掉。如果不写这一句算法依然能跑出正确结果但会做大量无用松弛性能明显下降。我实测过一个十万点级别的图加上这行判断后运行时间能砍掉将近一半。2.3 工程里用Dijkstra的几个真实坑第一个坑是重边处理。两个顶点之间可能有多条边邻接表里会存多条记录这本身没问题松弛时会自动取最短的那条。但如果你用邻接矩阵一定要在存边时取min否则后写入的边会覆盖前面的导致结果偏大。第二个坑是起点等于终点。有些实现会返回INF或者报错正确做法是直接返回0。这个边界在导航场景里很常见——用户点了同一个位置。第三个坑是大顶堆误用。Python的heapq是小根堆如果你不小心把距离取负再入堆出堆时忘了取反距离就全乱了。我见过不止一个同学栽在这上面。提示Dijkstra求出的dist数组是起点到所有点的最短距离。如果你只需要起点到某一个终点的距离可以在该点出堆时提前return能省下不少时间。3. Bellman-Ford能扛负权边还能顺手判负环3.1 松弛V-1轮的数学依据Bellman-Ford的思路比Dijkstra笨但更通用它对所有边做V-1轮松弛每一轮遍历图中每一条边尝试用u更新v。为什么是V-1轮因为一条最短路径最多包含V-1条边不含环含环只会更长或形成负环。每轮松弛至少能确定一层经过k条边的最短路V-1轮后所有最短路都被确定。它的复杂度是O(V·E)比Dijkstra慢但换来的是能处理负权边。这一点在很多实际场景里很关键比如某些费用模型里存在补贴性质的负代价。3.2 第V轮松弛为什么能判负环Bellman-Ford最漂亮的地方在于判负环。做完V-1轮后再对所有边做第V轮松弛。如果这一轮还能更新某个点的距离说明存在一条经过V条边还能变短的路径——这只能是因为图里有负环总权值为负的环绕着它转圈距离可以无限小。def bellman_ford(n, edges, start): # edges: [(u, v, w), ...] INF float(inf) dist [INF] * (n 1) dist[start] 0 for i in range(n - 1): updated False for u, v, w in edges: if dist[u] ! INF and dist[u] w dist[v]: dist[v] dist[u] w updated True if not updated: # 提前退出优化 break # 第n轮判负环 for u, v, w in edges: if dist[u] ! INF and dist[u] w dist[v]: return None # 存在负环 return dist注意那个updated标志的提前退出优化如果某一轮没有任何边被松弛说明已经收敛后面几轮纯属浪费。这个优化在稀疏图上效果很明显。3.3 一个容易搞错的细节负环可达性判负环时有个前提负环必须是从起点可达的。如果负环在另一个不连通的子图里它不影响起点到目标的最短路理论上不该报错。但上面这段代码里dist[u] ! INF这个判断保证了只有可达的点才会参与松弛所以不可达的负环不会被误判。这个细节很多人写的时候会漏导致明明起点到不了负环却报存在负环。另外要提醒的是Bellman-Ford判出负环后通常返回None或抛异常但工程里更常见的做法是记录下所有受负环影响的点因为存在负环和起点到终点这条路上有负环是两回事。4. SPFABellman-Ford的队列优化以及它为什么会被卡4.1 从每轮扫所有边到只扫被更新的点Bellman-Ford每轮都要遍历所有边但真正能引发更新的只有上一轮距离发生变化的那些点。SPFAShortest Path Faster Algorithm就是抓住这一点用一个队列维护距离刚被更新过、需要继续松弛邻居的顶点只有队列里的点出队时才去松弛它的邻居。from collections import deque def spfa(n, graph, start): INF float(inf) dist [INF] * (n 1) in_queue [False] * (n 1) cnt [0] * (n 1) # 记录每个点入队次数用于判负环 dist[start] 0 q deque([start]) in_queue[start] True while q: u q.popleft() in_queue[u] False for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w if not in_queue[v]: q.append(v) in_queue[v] True cnt[v] 1 if cnt[v] n: # 入队达到n次判定负环 return None return distin_queue数组的作用是防止同一个点重复入队这是SPFA性能的关键。cnt数组用来判负环一个点如果入队次数达到n次说明它被反复松弛必然存在负环。4.2 SPFA的复杂度真相平均快最坏很惨很多教程说SPFA复杂度是O(kE)k是平均每点入队次数通常是个小常数。这话没错但有个致命前提这是平均情况。在最坏情况下SPFA会退化到O(V·E)和Bellman-Ford一样慢。更麻烦的是出题人或者真实数据里存在专门卡SPFA的构造网格图、菊花图等特定结构能让SPFA的入队次数爆炸。我做过一个对比实验同样规模的随机图和精心构造的网格图SPFA的运行时间能差出两个数量级。所以在竞赛里如果题目没有负权边大家宁愿用堆优化Dijkstra如果有负权边又怕被卡就用Bellman-Ford或者更高级的算法。4.3 什么时候还值得用SPFA尽管有被卡的风险SPFA在工程里依然有它的位置。当图比较稀疏、数据没有恶意构造、又需要处理负权边时SPFA的实测速度通常远快于Bellman-Ford。另外SPFA的代码结构清晰容易加各种优化比如SLFSmall Label First把距离更小的点优先放队首和LLL优化。SLF的实现很简单入队时如果新点距离小于队首距离就插到队首否则插到队尾。这个改动在部分图上能明显减少入队次数。但要注意SLF不是万能的某些图上反而会变慢得实测。注意如果你的场景里根本没有负权边别用SPFA直接用堆优化Dijkstra稳定性和性能都更好。SPFA的价值只在有负权且数据友好这个窄区间里。5. Floyd多源最短路的暴力美学5.1 三重循环背后的动态规划Floyd解决的是任意两点间的最短距离也就是多源最短路。它的核心是三重循环代码短到只有五行def floyd(n, dist): # dist是n1阶邻接矩阵dist[i][j]初始为i到j的边权无边为INFdist[i][i]0 for k in range(1, n 1): for i in range(1, n 1): for j in range(1, n 1): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist它的本质是动态规划dist[i][j]表示只允许经过编号1到k的中间点时i到j的最短距离。外层循环k每增加一次就多允许一个中间点。当k遍历完所有点得到的就是全局最短路。5.2 循环顺序为什么不能乱Floyd最容易踩的坑就是循环顺序。k必须在最外层i和j在内层。如果你把i放最外层逻辑就变成了以i为起点逐步放宽中间点限制这跟DP的状态定义对不上结果会错。我见过有人为了看起来更符合直觉把i放外层跑出来的结果在小图上偶尔碰巧对大图上就崩了。记住k是阶段必须最外层。这是Floyd的铁律。5.3 稠密图上的性价比与负环检测Floyd的复杂度是O(V³)看起来很高但它的常数极小三重循环就是纯数组访问没有堆操作、没有队列。在V不超过几百的稠密图上Floyd往往比跑V次Dijkstra还快而且代码短、不易错。Floyd还能检测负环跑完之后检查对角线dist[i][i]如果存在某个i使得dist[i][i] 0说明存在经过i的负环。这个判断比Bellman-Ford更直接。另外Floyd天然支持负权边只要没有负环因为它不依赖贪心。但它同样不能处理负环因为负环会让最短路无意义。6. 四种算法横向对比与选型决策表把四个算法放在一起对比选型就清晰了。下面这张表是我根据实际项目经验整理的参数结论来自标准图论分析算法解决问题边权要求时间复杂度空间复杂度适用图规模Dijkstra堆优化单源最短路非负O((VE)logV)O(VE)大图、稀疏图Dijkstra朴素单源最短路非负O(V²)O(V²)小图、稠密图Bellman-Ford单源最短路判负环可负O(V·E)O(VE)中等规模、有负权SPFA单源最短路判负环可负平均O(kE)最坏O(V·E)O(VE)稀疏、数据友好Floyd多源最短路可负无负环O(V³)O(V²)小图、稠密、需全源选型决策可以按这个顺序问自己需要所有点对之间的最短路吗是→FloydV小或对每个点跑DijkstraV大且非负。有负权边吗没有→Dijkstra有→Bellman-Ford或SPFA。需要判负环吗需要→Bellman-Ford稳或SPFA快但可能被卡。图是稠密还是稀疏稠密小图→朴素Dijkstra或Floyd稀疏大图→堆优化Dijkstra。7. 我在实际项目里踩过的三个坑第一个坑是用Dijkstra处理带负权的费用图。当时一个物流成本模型里某些线路有返程补贴权重是负的。我图省事直接上了Dijkstra结果部分路线算出来的成本比真实值高。排查了半天才反应过来是负权导致的贪心失效。后来换成Bellman-Ford问题立刻消失。这个教训让我养成了一个习惯拿到图先检查边权符号。第二个坑是SPFA在网格图上超时。有个路径规划需求图是规则网格我用了SPFA想省事本地小数据跑得飞快一上真实规模就超时。后来分析发现网格图正是SPFA的天敌结构入队次数暴涨。改成堆优化Dijkstra后性能稳定了。所以如果你的图有规则结构慎用SPFA。第三个坑是Floyd的INF设置太小。有次我把INF设成了10^9结果两个INF相加溢出成负数导致松弛判断出错跑出一堆莫名其妙的最短路。正确做法是把INF设成一个足够大但两倍不会溢出的值比如用Python的float(inf)或者在C里用0x3f3f3f3f这种安全无穷大。这个细节在跨语言移植时特别容易翻车。8. 几个能直接抄的优化技巧最后分享几个我常用的优化都是实测有效的。堆优化Dijkstra里如果只需要单终点出堆时判断if u target: return d提前结束能省下大量无用计算。这个在导航场景里几乎是标配。Bellman-Ford的提前退出某轮无更新就break一定要加稀疏图上能省掉大半轮次。SPFA的SLF优化在部分图上有效但别盲目加先测再决定。Floyd如果只需要部分点对的距离可以只跑需要的i和j外层k照常。另外Floyd的邻接矩阵初始化时dist[i][i] 0这一句千万别漏否则自己到自己的距离会变成INF后续所有经过自己的路径都会算错。还有一个通用建议写完任何最短路算法先用小规模手工可验证的图跑一遍。比如四个点、五条边的小图自己拿纸笔算一遍最短路跟程序输出对一下。这一步花不了几分钟但能帮你抓出绝大多数初始化、循环顺序、边界处理的低级错误。我带的几个新人凡是跳过这步直接上大数据的最后都回来补课了。