1. 项目概述从“点”到“网”的思维跃迁搞了这么多年算法我越来越觉得图论是程序员思维从“线性”到“网络”的一个关键分水岭。之前我们处理数组、链表、树结构再复杂也大多有个清晰的“前驱后继”关系。但图不一样它描述的是“多对多”的复杂关系网络社交网络的好友关系、地图导航的路径规划、网络拓扑的数据传输背后都是图在支撑。而图论算法的核心任务之一就是解决“最短路径”问题从A点出发怎么走才能最快或成本最低地到达B点这次我们聚焦的“算法基础14”正是图论最短路径算法的入门精华包它一口气串联了四个经典算法Floyed弗洛伊德、Dijkstra迪杰斯特拉、Bellman-Ford贝尔曼-福特和SPFAShortest Path Faster Algorithm。这可不是简单的罗列而是一条清晰的认知升级路径。Floyed让你理解所有点对之间最短距离的全局计算思想Dijkstra则是在正权图上寻找单源最短路径的“贪心”典范当图中存在负权边时Bellman-Ford以其稳健的松弛操作成为可靠的后盾而SPFA则是Bellman-Ford的队列优化版本在多数情况下能跑得更快。掌握这四板斧你就能应对绝大多数面试和实际开发中遇到的加权图最短路径问题了。无论你是正在备战算法竞赛的学生还是工作中需要处理网络路由、资源调度、关系推荐的开发者这套组合拳都值得你投入时间彻底吃透。2. 核心算法思想与适用场景全解析在深入代码之前我们必须先弄清楚每个算法“为什么”存在以及它们各自的地盘在哪里。盲目套用算法就像用螺丝刀去敲钉子事倍功半。2.1 Floyed算法全局视野的“多源”最短路径Floyed算法的核心思想是动态规划它要解决的是“所有顶点对”之间的最短路径问题。想象一下你有一张城市交通图需要快速查出任意两个城市之间的最短驾车距离Floyed就是干这个的。它的思路非常巧妙我们假设顶点编号从1到n。算法维护一个二维数组dist[i][j]代表从点i到点j的当前已知最短距离。初始时dist[i][j]就是邻接矩阵中记录的边权如果i和j直接相连否则就是无穷大INF并且dist[i][i] 0。Floyed的三重循环是它的灵魂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] ! INF dist[k][j] ! INF dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } }这个k到底是什么你可以把它理解为“中转站”。整个算法的过程就是允许使用前1个顶点作为中转更新一遍最短距离再允许使用前2个顶点作为中转再更新一遍……直到允许使用所有n个顶点作为中转。当k循环完成后dist[i][j]存储的就是从i到j允许经过图中任意顶点的最短路径长度。它的优缺点和适用场景非常明确优点思想简单代码极其简短就三重循环能一次性求出所有点对的最短路径。缺点时间复杂度是O(n³)空间复杂度O(n²)。这意味着当顶点数n较大时比如超过500它的计算成本会变得非常高。适用场景稠密图边数接近n²且顶点规模不大通常n200时用它非常方便。或者在你确实需要所有点对最短路径结果时。注意Floyed算法不能处理带有“负权回路”的图即边权总和为负的环因为这样的图中不存在最短路径可以无限绕环使距离趋于负无穷。但它可以处理带有负权边但没有负权回路的图。2.2 Dijkstra算法正权图的“单源”贪心寻路如果说Floyed是上帝视角那Dijkstra就是一位从起点出发的稳健探索者。它解决的是“单源最短路径”问题从一个固定的源点s出发到图中所有其他顶点的最短距离。Dijkstra算法的核心是“贪心”策略。它维护一个集合S代表已经找到最短路径的顶点。初始时S中只有源点s。然后它不断地从尚未确定最短路径的顶点集合中选择一个距离源点s最近的顶点u将其加入S并用u去“松弛”其所有邻居顶点v的距离。为什么选择“最近”的顶点这里用到了一个关键性质在所有边权都为非负数的图中当前距离源点最近的那个顶点它的最短路径距离不可能再被其他更远的顶点更新了。这是Dijkstra算法正确性的基石也决定了它不能处理负权边。它的经典实现有两种邻接矩阵实现每次找最小距离顶点需要遍历所有顶点总复杂度O(n²)适合稠密图。邻接表 优先队列堆优化这是必须掌握的优化版本。我们用一个小根堆C中用priority_queue来维护当前未确定顶点的距离每次取堆顶距离最小的顶点只要O(log n)。总复杂度可以优化到O((nm) log n)其中m是边数适合稀疏图。适用场景边权均为非负的图且你只关心从一个源点到其他所有点的最短路径。这是实际应用中最常见的算法比如地图导航距离、时间成本均为正、网络路由协议如OSPF。2.3 Bellman-Ford算法负权图的可靠卫士当图中存在负权边时Dijkstra的贪心策略就失效了因为“当前最近”的顶点可能通过一个负权边变得更近。这时就需要Bellman-Ford算法。它的思想比Dijkstra更“暴力”也更具普适性对图中的所有边进行n-1轮松弛操作。每一轮都尝试用所有边去更新起点到各个顶点的最短距离。为什么是n-1轮因为在没有负权回路的情况下最短路径最多包含n-1条边否则就会重复经过某个顶点形成环而正权环不会使路径更短负权环不允许存在。算法结束后再进行第n轮松弛。如果第n轮还能成功松弛任何一条边那就说明图中存在负权回路从源点出发的最短路径无法定义。它的优缺点优点能够处理带有负权边的图并能检测出负权回路。代码实现简单不依赖于复杂的数据结构。缺点时间复杂度高达O(n*m)在稀疏图上也比堆优化的Dijkstra慢很多。适用场景图中存在负权边或者你需要检测负权回路。例如在某些金融网络、差分约束系统中边权可能代表增益或损耗允许为负。2.4 SPFA算法Bellman-Ford的队列优化SPFA (Shortest Path Faster Algorithm) 可以看作是Bellman-Ford的“聪明版”。Bellman-Ford每轮都无差别地松弛所有边效率低下。SPFA观察到只有那些在前一轮松弛中距离被更新的顶点才有可能在这一轮中去更新它的邻居。因此SPFA使用一个队列来维护这些“距离被更新过的顶点”。流程如下源点入队。取出队首顶点u松弛它的所有出边。如果某个邻居v的距离被更新了并且v不在当前队列中则将v入队。重复步骤2直到队列为空。这本质上是一个宽度优先搜索BFS的思想但队列中的顶点可能会重复入队。SPFA的平均时间复杂度被认为是O(km)其中k是一个常数在随机图上通常很小因此效率远高于朴素的Bellman-Ford。但在最坏情况下比如精心构造的网格图它可能退化到O(nm)和Bellman-Ford一样。适用场景同样是处理带有负权边的图且图中没有负权回路。在大多数非构造性数据中SPFA的效率很高是竞赛和笔试中处理负权图的常用选择。但它不稳定且无法直接判断负权回路需要记录每个顶点的入队次数超过n次则可能存在负环。3. 算法核心实现细节与代码剖析理解了思想我们来看看如何把它们变成可运行的代码。这里我会给出最经典和实用的实现并附上关键注释。3.1 Floyed算法的标准实现与路径记录Floyed的实现非常固定。我们通常用邻接矩阵存储图并用一个很大的数如0x3f3f3f3f代表无穷大INF。#include cstring using namespace std; const int N 210; // 根据题目最大顶点数设定 const int INF 0x3f3f3f3f; int dist[N][N]; int n, m; // n顶点数m边数 void floyed() { // 初始化 for (int i 1; i n; i) { for (int j 1; j n; j) { if (i j) dist[i][j] 0; else dist[i][j] INF; } } // 读入边 for (int i 0; i m; i) { int a, b, w; cin a b w; dist[a][b] min(dist[a][b], w); // 处理重边保留最短的 // 如果是无向图需要加上 dist[b][a] min(dist[b][a], w); } // 核心三重循环 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] INF dist[k][j] INF) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } } } }如何记录具体路径Floyed算法也可以记录路径需要额外一个path[i][j]数组在更新dist[i][j]时记录下这次更新是通过哪个中转点k实现的即path[i][j] k。查询i到j的路径时需要递归地查找path[i][j]拼接出完整路径。不过由于Floyed本身复杂度高且路径记录稍显繁琐在实际需要具体路径的场景下更常用的还是Dijkstra。3.2 Dijkstra算法的邻接表堆优化实现这是你必须熟练掌握的版本99%的正权图单源最短路问题都用它。#include cstring #include iostream #include queue #include vector using namespace std; typedef pairint, int PII; // first: 距离, second: 顶点编号 const int N 100010, INF 0x3f3f3f3f; int n, m; int h[N], e[N], w[N], ne[N], idx; // 邻接表存储图 int dist[N]; bool st[N]; // 标记是否已确定最短距离 void add(int a, int b, int c) { e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx; } int dijkstra(int start) { memset(dist, 0x3f, sizeof dist); dist[start] 0; priority_queuePII, vectorPII, greaterPII heap; // 小根堆 heap.push({0, start}); // 距离放前面pair默认按first排序 while (heap.size()) { auto t heap.top(); heap.pop(); int ver t.second, distance t.first; // 如果这个点之前已经用更短的距离更新过了当前这个是冗余的直接跳过 if (st[ver]) continue; st[ver] true; // 标记为已确定 // 用当前确定的点ver去更新它的所有邻居 for (int i h[ver]; i ! -1; i ne[i]) { int j e[i]; if (dist[j] distance w[i]) { dist[j] distance w[i]; heap.push({dist[j], j}); // 新的距离入堆 } } } // 如果dist[n]仍然是INF说明起点无法到达n号点 if (dist[n] INF) return -1; return dist[n]; } int main() { memset(h, -1, sizeof h); // 邻接表头初始化 cin n m; while (m--) { int a, b, c; cin a b c; add(a, b, c); // 如果是无向图需要 add(b, a, c); } cout dijkstra(1) endl; // 计算从1号点到n号点的最短距离 return 0; }几个关键点堆中冗余处理if (st[ver]) continue;这行至关重要。因为一个顶点可能被多次加入堆每次距离更新都加入但只有第一次从堆中取出时它的距离才是最终确定的最短距离。后续再取出的都是历史更大的值直接跳过。复杂度每个顶点最多入队出队一次被标记st后不再处理每次出队需要遍历其所有边。总操作次数约为遍历所有边每次堆操作O(log n)故为O(m log n)。无向图记得添加双向边。3.3 Bellman-Ford算法的标准实现与负环检测Bellman-Ford的模板性也很强通常用结构体数组存储所有边。#include cstring #include iostream using namespace std; const int N 510, M 10010, INF 0x3f3f3f3f; struct Edge { int a, b, w; } edges[M]; int n, m, k; // n点m边k代表最多经过k条边有时是问题限制 int dist[N]; int last[N]; // 备份数组防止“串联更新” int bellman_ford(int start) { memset(dist, 0x3f, sizeof dist); dist[start] 0; // 进行k次松弛操作如果求1到n不超过k条边的最短路 // 如果求普通最短路则进行n-1次 for (int i 0; i k; i) { memcpy(last, dist, sizeof dist); // 备份上一轮结果 for (int j 0; j m; j) { int a edges[j].a, b edges[j].b, w edges[j].w; // 使用上一轮的距离last[a]来更新避免本轮更新的结果影响同轮其他边 if (last[a] ! INF dist[b] last[a] w) { dist[b] last[a] w; } } } // 检测负权回路理论上再进行第n次松弛如果还能更新则有负环 // 但通常题目会说明这里返回结果 if (dist[n] INF / 2) return -INF; // 因为负权边更新INF可能会略微减小 return dist[n]; } int main() { cin n m k; for (int i 0; i m; i) { int a, b, w; cin a b w; edges[i] {a, b, w}; } int res bellman_ford(1); if (res -INF) puts(impossible); else cout res endl; return 0; }关键点解析备份数组last这是Bellman-Ford实现中非常容易出错的地方。在第i轮松弛中我们必须使用第i-1轮结束后的距离数组来更新本轮。如果直接用dist数组更新可能会出现“串联更新”即本轮刚被更新的点又立即去更新其他点这相当于在一次迭代中使用了超过一条边违背了“最多经过i条边”的限制当kn-1时求普通最短路影响不大但为了逻辑清晰和适应限制边数的问题强烈建议始终使用备份。负环检测上述代码完成了k次松弛。如果要检测从起点出发是否能到达负环可以在kn-1次松弛后再执行一次松弛操作第n次如果任何一条边还能被松弛则说明存在从起点可达的负权回路。INF判断由于存在负权边dist可能从INF被更新为一个略小于INF的值如INF - 5。所以判断不可达时常用if (dist[n] INF / 2)而不是dist[n] INF。3.4 SPFA算法的队列优化实现SPFA的实现和BFS很像但需要维护距离数组。#include cstring #include iostream #include queue using namespace std; const int N 100010, INF 0x3f3f3f3f; int n, m; int h[N], e[N], w[N], ne[N], idx; int dist[N]; bool st[N]; // 标记顶点是否在队列中防止重复入队 void add(int a, int b, int c) { e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx; } int spfa(int start) { memset(dist, 0x3f, sizeof dist); dist[start] 0; queueint q; q.push(start); st[start] true; // 在队列中 while (q.size()) { int t q.front(); q.pop(); st[t] false; // 出队标记为不在队列中 // 遍历t的所有出边 for (int i h[t]; i ! -1; i ne[i]) { int j e[i]; if (dist[j] dist[t] w[i]) { dist[j] dist[t] w[i]; // 如果j不在队列中则入队 if (!st[j]) { q.push(j); st[j] true; } } } } if (dist[n] INF) return -INF; return dist[n]; } // 判断是否存在负环从任意点出发可达的负环 bool spfa_negative_cycle() { // 初始化所有点距离为0并全部入队 // 因为负环可能从任意点出发所以需要把所有点都作为起点考虑 queueint q; for (int i 1; i n; i) { q.push(i); st[i] true; } int cnt[N] {0}; // 记录每个顶点的入队松弛次数 while (q.size()) { int t q.front(); q.pop(); st[t] false; for (int i h[t]; i ! -1; i ne[i]) { int j e[i]; if (dist[j] dist[t] w[i]) { dist[j] dist[t] w[i]; cnt[j] cnt[t] 1; // 更新松弛次数 if (cnt[j] n) return true; // 如果松弛次数达到n说明有负环 if (!st[j]) { q.push(j); st[j] true; } } } } return false; } int main() { memset(h, -1, sizeof h); cin n m; while (m--) { int a, b, c; cin a b c; add(a, b, c); } int res spfa(1); if (res -INF) puts(impossible); else cout res endl; return 0; }SPFA的要点st数组的作用st在这里标记顶点是否在队列中而不是像Dijkstra那样标记是否“已确定”。目的是防止同一个顶点在距离被多次更新时被重复加入队列造成无效操作。一个顶点出队后如果后续又被其他点更新了距离它可以再次入队。负环检测通用的SPFA负环检测需要做一些改动。我们需要初始化所有点的距离为0相当于建立一个“超级源点”连向所有点且边权为0并全部入队。然后记录每个顶点被松弛的次数cnt。根据Bellman-Ford原理最短路径最多经过n-1条边因此一个顶点最多被松弛入队n-1次。如果某个顶点的入队次数达到n则说明存在负环。注意这里的dist数组初始值不影响负环的判断因为负环的存在会使距离不断减小。效率在随机图上SPFA通常很快。但在某些特殊构造的图如网格图、菊花图上它可能退化到O(nm)。因此在正权图问题上保险起见优先使用Dijkstra。4. 四大算法对比与选型指南纸上得来终觉浅绝知此事要躬行。理解了原理和代码我们还需要一张清晰的“决策地图”来指导我们在不同场景下该用哪个算法。特性维度Floyed (弗洛伊德)Dijkstra (迪杰斯特拉)Bellman-Ford (贝尔曼-福特)SPFA (队列优化的Bellman-Ford)核心思想动态规划逐步允许更多中转点贪心 广度优先每次选最近点动态规划/松弛进行n-1轮全局松弛BFS思想用队列维护待松弛点解决问题多源最短路径单源最短路径单源最短路径单源最短路径边权限制不能有负权回路必须全为非负权可以处理负权边能检测负权回路可以处理负权边能检测负权回路时间复杂度O(n³)朴素O(n²)堆优化O(m log n)O(n*m)平均O(km)最坏O(n*m)空间复杂度O(n²)邻接表O(nm)O(m) (存边)邻接表O(nm)优势场景稠密图顶点少需所有点对距离正权图单源最短路的标准答案负权图带边数限制的最短路理论清晰负权图在随机数据上效率高代码复杂度极简三重循环堆优化中等简单中等是否稳定稳定稳定稳定不稳定可能被卡选型决策流程第一步确定问题类型需要所有点对之间的最短路径- 考虑Floyed。但务必先看顶点数n如果n500就要警惕O(n³)的复杂度可能超时。只需要从一个起点到其他点的最短路径- 进入第二步。第二步检查边权图中所有边权都是非负数- 毫不犹豫选择堆优化Dijkstra。这是效率最高、最稳定的方案。图中存在负权边- 进入第三步。第三步处理负权边如果题目明确保证没有负权回路且你对效率有要求比如竞赛可以尝试SPFA。但要知道它有被特殊数据卡的风险。如果题目需要检测负权回路或者你追求代码的稳定性和普适性比如笔试、工程使用Bellman-Ford。它的O(n*m)复杂度是稳定的上界。如果问题有**“最多经过k条边”**的限制必须使用Bellman-Ford并且配合备份数组last来实现。一句话口诀正权单源用Dijkstra负权检测用Ford全源小图用Floyed随机负权试SPFA。5. 实战中的常见“坑点”与调试技巧理论很美好调试很残酷。下面这些是我和很多同行在实战中踩过的坑希望能帮你省下几个小时甚至几天的调试时间。5.1 无穷大INF的设定与判断这是一个初学者极易出错的地方。设定通常用0x3f3f3f3f。这个数约等于10^9满足大多数题目对边权范围的要求一般不超过10^9。更重要的是0x3f3f3f3f的每个字节都是0x3f用memset(dist, 0x3f, sizeof dist)可以快速将整个数组初始化为这个值。而且两个0x3f3f3f3f相加不会溢出到负数仍在int范围内。判断在Dijkstra (正权图)中如果dist[t] INF可以认为从起点无法到达t点。在Bellman-Ford/SPFA (可能有负权)中由于负权边的存在INF可能被更新为一个略小于INF的值例如INF - 5。此时判断不可达应该用if (dist[t] INF / 2)。这是一个经验值因为边权之和通常不会大到使INF减少超过一半。5.2 重边和自环的处理图的输入数据往往不是“干净”的。重边两个顶点之间可能存在多条直接相连的边且权值不同。对于最短路径问题我们显然只关心权值最小的那条。邻接矩阵在读入边时使用g[a][b] min(g[a][b], w)。邻接表直接添加多条边即可算法本身如Dijkstra在松弛时会自动选取最小的那条因为我们会用min操作更新dist。自环从自己指向自己的边。在正权图中自环权值为正不会影响结果因为dist[i] w dist[i]。在负权图中负权自环会形成负环需要算法检测出来。5.3 无向图与有向图这是一个概念性错误但一旦写错调试起来非常痛苦。无向图意味着边是双向的。在存储时需要添加两条有向边add(a, b, w); add(b, a, w);。很多题目描述是“道路”这通常暗示是无向图。而“单向街道”、“航线”则是有向图。务必仔细审题。5.4 Dijkstra堆优化中的“冗余点”判断这是堆优化Dijkstra的灵魂代码也是我见过最多的错误之一。auto t heap.top(); heap.pop(); int ver t.second, distance t.first; if (st[ver]) continue; // 就是这行 st[ver] true; ...为什么必须有这行因为一个顶点ver的距离可能被多次更新每次更新都会将其{new_dist, ver}压入堆中。但只有第一次从堆中弹出的那个distance才是它最终确定的最短距离。后面再弹出的同顶点ver其distance必然大于或等于之前确定的值是“冗余”的。如果不跳过就会用这个过时的、更大的距离去松弛邻居虽然不会导致错误结果因为dist[j] distance w条件可能不成立但会做大量无用功严重降低效率甚至可能导致超时。5.5 Bellman-Ford的“串联更新”问题在有限制边数比如最多经过k条边的最短路问题中必须使用备份数组last。memcpy(last, dist, sizeof dist); // 备份上一轮的结果 for (所有边) { // 用last[a]来更新dist[b]而不是用dist[a] if (last[a] ! INF dist[b] last[a] w) { dist[b] last[a] w; } }如果不备份在同一轮循环中前面边更新的dist[a]可能会被后面的边用到这就相当于一条路径在本次迭代中使用了超过一条边违反了“最多经过i条边”的限制。5.6 调试技巧打印状态与构造小数据当你的程序输出错误或者超时时打印中间状态在算法关键步骤后打印dist数组。对比手动模拟的小样例看看是从哪一步开始出错的。构造最小反例如果提交后WAWrong Answer尝试自己构造一个小的测试用例n3, m4这种手动计算正确结果然后看你的程序输出是什么。这是定位逻辑错误最有效的方法。检查初始化dist数组、邻接表头h数组是否初始化了INF设置是否正确检查输入是无向图还是有向图有没有处理重边顶点编号是从0开始还是1开始复杂度估算在动手前先根据题目给的n和m的范围估算一下你选择的算法是否会超时。比如n1000Floyed的O(10^9)运算量基本会超时。6. 从算法到应用典型场景延伸思考掌握了这四种算法就像拿到了四把不同的钥匙可以打开许多实际问题的大门。Dijkstra的变种它求的是最短距离但如果边权代表的是时间、成本、风险概率呢只要权值非负且你定义的“最短”满足可加性和非负性距离距离还是距离且不为负Dijkstra的思想依然适用。例如在网络延迟、物流成本计算中广泛应用。Floyed的额外收获Floyed算法结束后得到的dist矩阵不仅是距离还可以用来解决“传递闭包”问题。如果把边权定义为“是否连通”连通为1不连通为INF那么Floyed算法就可以判断图中任意两点是否连通dist[i][j] INF则连通。这常用于社交网络中的“朋友的朋友”关系推断。Bellman-Ford与差分约束这是Bellman-Ford算法一个非常重要的应用领域。差分约束系统将一系列形如x_i - x_j c_k的不等式转化为图论中的边(j - i, 权值 c_k)。求该系统的一个可行解等价于在图中添加一个超级源点后求该点到所有点的最短路径如果存在负环则无解。这为许多涉及不等式约束的规划问题提供了高效的图论解法。SPFA与网络流在一些网络流算法如最小费用最大流中需要频繁地在残量网络上寻找最短最小费用增广路。由于费用可能为负回流Dijkstra无法使用而SPFA因其在一般图上的高效性常被用作寻找最短增广路的子过程。算法的学习从来不是孤立的。把这四个最短路径算法吃透你不仅解决了“怎么走最短”的问题更重要的是你掌握了“贪心”、“动态规划”、“松弛”、“迭代逼近”这些核心的算法设计思想。下次当你遇到一个新的、看似复杂的问题时不妨想想这个问题能建模成图吗顶点和边代表什么权值是什么求的是什么一旦完成了这个建模过程你的武器库里就已经有现成的工具可以选择了。