最短路径之Bellman-Ford算法文章目录最短路径之Bellman-Ford算法一、前言二、最短路径2.1 最短路算法2.2 Floyed算法2.2.1 概述2.2.2 代码2.2.3 时间复杂度2.3 Dijkstra算法2.3.1 概述2.3.2 代码2.3.3 时间复杂度2.3.4 Dijkstra算法和Floyed算法的共性2.4 优化1-Bellman-Ford算法2.4.1 概述2.4.2 代码2.4.3 时间复杂度2.4.4 用法2.4.5 缺点2.5 优化2-链式前向星实现的邻接表存图堆优化版的Dijkstra算法2.5.1 概述2.5.2 代码2.5.3时间复杂度2.6 优化3-SPFA算法2.6.1 概述2.6.2 代码2.6.3 时间复杂度2.7 注意2.8 例题2.8.1 洛谷三、小结一、前言今天是最短路径~二、最短路径2.1 最短路算法算法单源/多源负边权负边权回路Floyed算法多源可以不可以Dijkstra算法单源不可以不可以Bellman-Ford算法单源可以不可以SPFA算法单源可以不可以重点关注算法流程/思路、时间复杂度、使用情况单源/多源负边权/负边权回路负边权回路越走越短但是永远到不了终点2.2 Floyed算法2.2.1 概述基于动态规划后面详细讲可以计算图中任意两点间的最短路径多源最短路2.2.2 代码// 初始化// 点u,v有边相连dis[u][v]w[u][v];// 点u,v不相连dis[u][v]0x7fffffff;for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){if(dis[i][j]dis[i][k]dis[k][j])dis[i][j]dis[i][k]dis[k][j];}}}// dis[i][j]得出的就是从i到j的最短路径2.2.3 时间复杂度O( | v | ^ 3 )2.3 Dijkstra算法2.3.1 概述基于贪心用来计算一个点到其他任意点的最短路径的算法也就是说只能计算起点只有一个的情况。不能处理存在负边权的情况。假设起点是sdis[i] /dis[s][i]表示s到i的最短路径的距离w[i][j]表示边i, j的权值用i做中转点来不断缩短s到j的距离。此操作称作松弛relax在Dijkstra算法中对每条边执行一次松弛操作贪心 松弛2.3.2 代码// 设起点为s,dis[v]表示从s到v的最短路径pre[v]为v的前驱节点用来输出路径// 初始化dis[v]0x7fffffff;// v!sdis[s]0;// 起点自己到自己肯定是0pre[s]0;for(inti1;in;i){// 1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的// 2.u标记为已确定最短路径// 3.for 与u相连的每个未确定最短路径的顶点v(即遍历u的邻接点){if(dis[u]w[u][v]dis[v]){dis[v]dis[u]w[u][v];pre[v]u;}}}2.3.3 时间复杂度O( | v | ^ 2 )2.3.4 Dijkstra算法和Floyed算法的共性都找到了一个中转点一个是贪心离起点最近的就是中转点另一个是枚举2.4 优化1-Bellman-Ford算法2.4.1 概述不再找中转点了枚举边每次将边的起点作为中转点松弛该边边的终点作为最短路的终点。不断枚举边距离不变时终止2.4.2 代码// 设s为起点dis[v]即为s到v的最短距离pre[v]为v前驱不需要就不用pre// w[j]是边j的长度且j连接u、v// 初始化dis[s]0;dis[v]0x7fffffff;// v!spre[s]0;for(inti1;in-1;i)// 多少轮松弛操作for(intj1;j边数;j)// 注意要枚举所有边不能枚举点if(dis[u]w[j]dis[v])// u、v分别是这条边连接的两个点{dis[v]dis[u]w[j];pre[v]u;}完整版#includebits/stdc.h#defineLLlonglongusingnamespacestd;intn,m;// n个点m条边intdis[105];ints;// 起点structEdge{inta,b,w;// 起点a终点b权值w}e[10005];// 边集数组来存图voidford(){intx,y,w;boolflag0;// 标记是否松弛for(inti1;in;i){flag0;for(intj0;jm;j){xe[j].a;ye[j].b;we[j].w;if(dis[x]wdis[y]){dis[y]dis[x]w;// pre[y] x;flag1;}// dis[y]min(dis[y],dis[x]w);}if(flag0)// 说明遍历所有边之后没有松弛{break;// 减少几次对边的遍历}}if(flag1)// 循环到n轮还可以进行松弛说明存在负边权回路{cout有负权回路endl;}else{cout没有负权回路endl;}}intmain(){scanf(%d %d,n,m);// 读入nmfor(inti0;im;i)// 读入m条边{scanf(%d %d %d,e[i].a,e[i].b,e[i].w);}scanf(%d,s);// 读入起点smemset(dis,0x3f,sizeof(dis));// 设置距离为无穷大dis[s]0;ford();for(inti1;in;i){printf(%d ,dis[i]);}return0;}// 测试数据//5 5//2 3 2//1 2 -3//1 5 5//4 5 2//3 4 3//10x7fffffff是int的最大值(2^31-1)0x是指16进制7是0111每一个16进制位表示4个二进制位0111 1111 1111 1111 1111 1111 1111 11110x3f比0x7fffffff的一半少一些目的是为了防止disw越界int2.4.3 时间复杂度O( | v || e | )最短路的边数最多为v - 1,最多进行 |v|-1轮松弛操作2.4.4 用法求最短路径判断是否存在负边权回路2.4.5 缺点不是特别稳定时间复杂度取决于建边顺序如果可以每次松弛一定可以被松弛的边就好了于是它的优化版本就是SPFA算法2.5 优化2-链式前向星实现的邻接表存图堆优化版的Dijkstra算法2.5.1 概述针对在没有被访问的点中找一个顶点u使得dis[u]是最小的这个步骤利用优先队列最小堆实现需要注意点可能重复入队具有两条最短路径continue2.5.2 代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;intn,m,cnt;intflag[105];// // 标记顶点是否已确定最短距离intdis[105];ints;// 起点structEdge{intto,next,w;}e[10005];// 边集数组inthead[105];priority_queuePII,vectorPII,greaterPIIq;voidadd(intx,inty,intw){e[cnt].toy;e[cnt].ww;e[cnt].nexthead[x];head[x]cnt;cnt;}voiddijkstra(){memset(dis,0x3f,sizeof(dis));dis[s]0;// 0 sq.push({dis[s],s});// { }已经表示pair了/* pairint,int z; z.first dis[s]; z.second s; q.push(z); */while(q.size()){PII tq.top();q.pop();intut.second;intdt.first;if(flag[u]1){continue;}flag[u]1;for(intihead[u];i!-1;ie[i].next){// i即u的出边intve[i].to;// u的邻接点if(flag[v]0dis[v]dis[u]e[i].w){dis[v]dis[u]e[i].w;q.push({dis[v],v});}}}}intmain(){scanf(%d %d %d,n,m,s);intx,y,w;memset(head,-1,sizeof(head));for(inti1;im;i){scanf(%d %d %d,x,y,w);add(x,y,w);}dijkstra();for(inti1;in;i){printf(%d ,dis[i]);}return0;}2.5.3时间复杂度O((|v||e|)* log|v|) 主要看Dijkstra算法2.6 优化3-SPFA算法2.6.1 概述如何明确在一轮循环中哪条边可以松弛每一轮遍历中松弛的点是上一轮被松弛点的邻接点即找上一轮被松弛点的邻接点。则采用队列进行优化将松弛的点入队每次只找队列中的邻接点进行松弛。2.6.2 代码#includebits/stdc.h#defineLLlonglongusingnamespacestd;intn,m,cnt;intflag[105];intdis[105];intuse[105];// 记录每个点被用过多少次ints;// 起点structEdge{intto,next,w;}e[10005];inthead[105];// 链式前向星存图voidadd(intx,inty,intw){e[cnt].toy;e[cnt].ww;e[cnt].nexthead[x];head[x]cnt;cnt;}voidSPFA(){queueintq;// 申请一个队列memset(dis,0x3f,sizeof(dis));dis[s]0;flag[s]1;// 标记s点有没有被放入队列一个点可能被放入队列多次// 就是标记s在上一轮中有没有被松弛的use[s];q.push(s);while(!q.empty()){intuq.front();q.pop();flag[u]0;for(intihead[u];i-1;ie[i].next){intve[i].to;// v就是u的邻接点if(flag[v]0dis[v]dis[u]e[i].w){dis[v]dis[u]e[i].w;q.push(v);use[v];flag[v]1;//if(use[v]n) // 入队n次就是存在环//{// printf...//}}}}}intmain(){scanf(%d %d %d,n,m,s);intx,y,w;memset(head,-1,sizeof(head));for(inti1;im;i){scanf(%d %d %d,x,y,w);add(x,y,w);}SPFA();for(inti1;in;i){printf(%d ,dis[i]);}return0;}2.6.3 时间复杂度O(|v| * |e|)不稳定2.7 注意无负边权单源最短路堆优化Dijkstra算法多源最短路Floyed算法负边权单源最短路SPFA算法/Ford算法2.8 例题2.8.1 洛谷P8802 [蓝桥杯 2022 国 B] 出差P1462 通往奥格瑞玛的道路三、小结本篇结合洛谷官方书籍、灵神题单等以及我的思考~
最短路径之Bellman-Ford算法
发布时间：2026/7/7 22:33:27
最短路径之Bellman-Ford算法文章目录最短路径之Bellman-Ford算法一、前言二、最短路径2.1 最短路算法2.2 Floyed算法2.2.1 概述2.2.2 代码2.2.3 时间复杂度2.3 Dijkstra算法2.3.1 概述2.3.2 代码2.3.3 时间复杂度2.3.4 Dijkstra算法和Floyed算法的共性2.4 优化1-Bellman-Ford算法2.4.1 概述2.4.2 代码2.4.3 时间复杂度2.4.4 用法2.4.5 缺点2.5 优化2-链式前向星实现的邻接表存图堆优化版的Dijkstra算法2.5.1 概述2.5.2 代码2.5.3时间复杂度2.6 优化3-SPFA算法2.6.1 概述2.6.2 代码2.6.3 时间复杂度2.7 注意2.8 例题2.8.1 洛谷三、小结一、前言今天是最短路径~二、最短路径2.1 最短路算法算法单源/多源负边权负边权回路Floyed算法多源可以不可以Dijkstra算法单源不可以不可以Bellman-Ford算法单源可以不可以SPFA算法单源可以不可以重点关注算法流程/思路、时间复杂度、使用情况单源/多源负边权/负边权回路负边权回路越走越短但是永远到不了终点2.2 Floyed算法2.2.1 概述基于动态规划后面详细讲可以计算图中任意两点间的最短路径多源最短路2.2.2 代码// 初始化// 点u,v有边相连dis[u][v]w[u][v];// 点u,v不相连dis[u][v]0x7fffffff;for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){if(dis[i][j]dis[i][k]dis[k][j])dis[i][j]dis[i][k]dis[k][j];}}}// dis[i][j]得出的就是从i到j的最短路径2.2.3 时间复杂度O( | v | ^ 3 )2.3 Dijkstra算法2.3.1 概述基于贪心用来计算一个点到其他任意点的最短路径的算法也就是说只能计算起点只有一个的情况。不能处理存在负边权的情况。假设起点是sdis[i] /dis[s][i]表示s到i的最短路径的距离w[i][j]表示边i, j的权值用i做中转点来不断缩短s到j的距离。此操作称作松弛relax在Dijkstra算法中对每条边执行一次松弛操作贪心 松弛2.3.2 代码// 设起点为s,dis[v]表示从s到v的最短路径pre[v]为v的前驱节点用来输出路径// 初始化dis[v]0x7fffffff;// v!sdis[s]0;// 起点自己到自己肯定是0pre[s]0;for(inti1;in;i){// 1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的// 2.u标记为已确定最短路径// 3.for 与u相连的每个未确定最短路径的顶点v(即遍历u的邻接点){if(dis[u]w[u][v]dis[v]){dis[v]dis[u]w[u][v];pre[v]u;}}}2.3.3 时间复杂度O( | v | ^ 2 )2.3.4 Dijkstra算法和Floyed算法的共性都找到了一个中转点一个是贪心离起点最近的就是中转点另一个是枚举2.4 优化1-Bellman-Ford算法2.4.1 概述不再找中转点了枚举边每次将边的起点作为中转点松弛该边边的终点作为最短路的终点。不断枚举边距离不变时终止2.4.2 代码// 设s为起点dis[v]即为s到v的最短距离pre[v]为v前驱不需要就不用pre// w[j]是边j的长度且j连接u、v// 初始化dis[s]0;dis[v]0x7fffffff;// v!spre[s]0;for(inti1;in-1;i)// 多少轮松弛操作for(intj1;j边数;j)// 注意要枚举所有边不能枚举点if(dis[u]w[j]dis[v])// u、v分别是这条边连接的两个点{dis[v]dis[u]w[j];pre[v]u;}完整版#includebits/stdc.h#defineLLlonglongusingnamespacestd;intn,m;// n个点m条边intdis[105];ints;// 起点structEdge{inta,b,w;// 起点a终点b权值w}e[10005];// 边集数组来存图voidford(){intx,y,w;boolflag0;// 标记是否松弛for(inti1;in;i){flag0;for(intj0;jm;j){xe[j].a;ye[j].b;we[j].w;if(dis[x]wdis[y]){dis[y]dis[x]w;// pre[y] x;flag1;}// dis[y]min(dis[y],dis[x]w);}if(flag0)// 说明遍历所有边之后没有松弛{break;// 减少几次对边的遍历}}if(flag1)// 循环到n轮还可以进行松弛说明存在负边权回路{cout有负权回路endl;}else{cout没有负权回路endl;}}intmain(){scanf(%d %d,n,m);// 读入nmfor(inti0;im;i)// 读入m条边{scanf(%d %d %d,e[i].a,e[i].b,e[i].w);}scanf(%d,s);// 读入起点smemset(dis,0x3f,sizeof(dis));// 设置距离为无穷大dis[s]0;ford();for(inti1;in;i){printf(%d ,dis[i]);}return0;}// 测试数据//5 5//2 3 2//1 2 -3//1 5 5//4 5 2//3 4 3//10x7fffffff是int的最大值(2^31-1)0x是指16进制7是0111每一个16进制位表示4个二进制位0111 1111 1111 1111 1111 1111 1111 11110x3f比0x7fffffff的一半少一些目的是为了防止disw越界int2.4.3 时间复杂度O( | v || e | )最短路的边数最多为v - 1,最多进行 |v|-1轮松弛操作2.4.4 用法求最短路径判断是否存在负边权回路2.4.5 缺点不是特别稳定时间复杂度取决于建边顺序如果可以每次松弛一定可以被松弛的边就好了于是它的优化版本就是SPFA算法2.5 优化2-链式前向星实现的邻接表存图堆优化版的Dijkstra算法2.5.1 概述针对在没有被访问的点中找一个顶点u使得dis[u]是最小的这个步骤利用优先队列最小堆实现需要注意点可能重复入队具有两条最短路径continue2.5.2 代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;intn,m,cnt;intflag[105];// // 标记顶点是否已确定最短距离intdis[105];ints;// 起点structEdge{intto,next,w;}e[10005];// 边集数组inthead[105];priority_queuePII,vectorPII,greaterPIIq;voidadd(intx,inty,intw){e[cnt].toy;e[cnt].ww;e[cnt].nexthead[x];head[x]cnt;cnt;}voiddijkstra(){memset(dis,0x3f,sizeof(dis));dis[s]0;// 0 sq.push({dis[s],s});// { }已经表示pair了/* pairint,int z; z.first dis[s]; z.second s; q.push(z); */while(q.size()){PII tq.top();q.pop();intut.second;intdt.first;if(flag[u]1){continue;}flag[u]1;for(intihead[u];i!-1;ie[i].next){// i即u的出边intve[i].to;// u的邻接点if(flag[v]0dis[v]dis[u]e[i].w){dis[v]dis[u]e[i].w;q.push({dis[v],v});}}}}intmain(){scanf(%d %d %d,n,m,s);intx,y,w;memset(head,-1,sizeof(head));for(inti1;im;i){scanf(%d %d %d,x,y,w);add(x,y,w);}dijkstra();for(inti1;in;i){printf(%d ,dis[i]);}return0;}2.5.3时间复杂度O((|v||e|)* log|v|) 主要看Dijkstra算法2.6 优化3-SPFA算法2.6.1 概述如何明确在一轮循环中哪条边可以松弛每一轮遍历中松弛的点是上一轮被松弛点的邻接点即找上一轮被松弛点的邻接点。则采用队列进行优化将松弛的点入队每次只找队列中的邻接点进行松弛。2.6.2 代码#includebits/stdc.h#defineLLlonglongusingnamespacestd;intn,m,cnt;intflag[105];intdis[105];intuse[105];// 记录每个点被用过多少次ints;// 起点structEdge{intto,next,w;}e[10005];inthead[105];// 链式前向星存图voidadd(intx,inty,intw){e[cnt].toy;e[cnt].ww;e[cnt].nexthead[x];head[x]cnt;cnt;}voidSPFA(){queueintq;// 申请一个队列memset(dis,0x3f,sizeof(dis));dis[s]0;flag[s]1;// 标记s点有没有被放入队列一个点可能被放入队列多次// 就是标记s在上一轮中有没有被松弛的use[s];q.push(s);while(!q.empty()){intuq.front();q.pop();flag[u]0;for(intihead[u];i-1;ie[i].next){intve[i].to;// v就是u的邻接点if(flag[v]0dis[v]dis[u]e[i].w){dis[v]dis[u]e[i].w;q.push(v);use[v];flag[v]1;//if(use[v]n) // 入队n次就是存在环//{// printf...//}}}}}intmain(){scanf(%d %d %d,n,m,s);intx,y,w;memset(head,-1,sizeof(head));for(inti1;im;i){scanf(%d %d %d,x,y,w);add(x,y,w);}SPFA();for(inti1;in;i){printf(%d ,dis[i]);}return0;}2.6.3 时间复杂度O(|v| * |e|)不稳定2.7 注意无负边权单源最短路堆优化Dijkstra算法多源最短路Floyed算法负边权单源最短路SPFA算法/Ford算法2.8 例题2.8.1 洛谷P8802 [蓝桥杯 2022 国 B] 出差P1462 通往奥格瑞玛的道路三、小结本篇结合洛谷官方书籍、灵神题单等以及我的思考~
 获取与实战)
