【最短路算法】第二弹：一文弄懂Bellman |
您所在的位置：网站首页 › 贝尔曼福德算法 › 【最短路算法】第二弹：一文弄懂Bellman |
【最短路算法】第二弹：一文弄懂Bellman
|
前天，我们学习了Dijkstra算法：【最短路算法】一篇文章彻底弄懂Dijkstra算法|多图解+代码详解 Dijstra算法用于计算单源、正权边的最短路问题 今天学习的贝尔曼福特算法，是用于计算单源，且可含负权边的最短路问题 目录 💐前言🌻一、Bellman-Ford算法简介🌻二、算法思路总结 🌻二、算法原理👩🏫为啥能求最短路？为啥迭代次数有意义？👩🏫串联问题 🌻三、加深理解-题目训练输入格式输出格式数据范围输入样例：输出样例： 🌻一、Bellman-Ford算法简介 用于求解单源、有负权边的最短路问题实现通过m次迭代求出从起点到终点不超过m条边构成的最短路径其优于Dijkstra的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。时间复杂度是O(nm)🍼与迪杰斯特拉算法的区别： 迪杰斯特拉算法是借助贪心思想，每次选取一个未处理的最近的结点，去对与他相连接的边进行松弛操作；贝尔曼福特算法是直接对所有边进行N-1遍松弛操作。 迪杰斯特拉算法要求边的权值不能是负数；贝尔曼福特算法边的权值可以为负数，并可检测负权回路。 名词解释： 1. 松弛操作：不断更新最短路径和前驱结点的操作。 2. 负权回路：绕一圈绕回来发现到自己的距离从0变成了负数，到各结点的距离无限制的降低，停不下来 🌻二、算法思路🛫思路 初始化源点s到各个点v的路径dis[v] = ∞，dis[s] = 0。 进行n - 1次遍历，每次遍历对所有边进行松弛操作，满足则将权值更新。 松弛操作：以a为起点，b为终点，ab边长度为w为例。dis[a]代表源点s到a点的路径长度，dis[b]代表源点s到b点的路径长度。如果满足下面的式子则将dis[b]更新为dis[a] + w。 dis[b] > dis[a] + w 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路。 🌱算法模板 int n, m; // n表示点数，m表示边数 int dist[N]; // dist[x]存储1到x的最短路距离 struct Edge // 边，a表示出点，b表示入点，w表示边的权重 { int a, b, w; }edges[M]; // 求1到n的最短路距离，如果无法从1走到n，则返回-1。 int bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } } if (dist[n] > 0x3f3f3f3f / 2) return -1; return dist[n]; } 总结Bellman-ford算法的思路也很简单，直接就是两层循环，内层循环所有边，外层循环就是循环所有边的次数，这个外层循环次数一般是题目控制的。时间复杂度是O(n*m) 🚏注意点 循环n次之后对所有的边一定满足dist[b] memset(dist,0x3f,sizeof(dist));//初始化dist数组 dist[1] = 0; for(int i = 0; i //遍历所有边 auto e = edges[j]; dist[e.b] = min(dist[e.b],last[e.a] + e.w);//松驰操作 } } } int main(){ scanf("%d%d%d",&n,&m,&k);//n个顶点，m条边，k是限制边数 for(int i = 0; i a,b,w}; } bellman_ford(); if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n",dist[n]); return 0; } 在上面代码中，是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可
|
【本文地址】
今日新闻 |
推荐新闻 |