赞
踩
Bellman-ford算法是一种求解“单源最短路径”算法,单源最短路就是求一个源点到其他结点的最短路径。而Bellman-ford算法最核心的思想就是“松弛操作”。我们用下图来具体操作一下Bellman-ford。
首先,我们定义一个dis[ i ]数组, dis数组的意义是源点到其他点的经过边数不超过k(松弛操作次数)的最短距离。 假定 1号顶点是源点,则初始化dis[1] = 0; 其他点的距离初始化为无穷大。
然后开始第一轮松弛,遍历全部边,首先遍历第一条边进行松弛 2 - > 3, 其权值为2。松弛操作就是 : 试一试用 源点 到2号顶点 的距离 加上 2 -> 3的权值,能否缩小 源点 到 3号顶点 的距离。 现在开始进行松弛, 我们发现dis[2] 和 dis[3] 都是无穷大, 那么此时 源点 到 2号顶点 ,3号顶点 的距离都是无穷大。说明我们不能达到2号顶点,所以我们不可以使用 2->3 这条边进行松弛。
然后遍历第2条边, 1 -> 2 ,权值-3。 此时我们发现可以通过 这条边来松弛 源点 到 2号结点 的距离,因为 dis[2] > dis[1] + -3(权值)。第一轮松弛结束后,得到新的结果 ,如下图
然后我们再次遍历所有边,进行第二轮松弛, 也是首先遍历第一条边 2 -> 3 权值为2. 我们此时发现通过这条边可以松弛 源点 到 3号顶点 的距离, 因为 dis[3] > dis[2] + 2 并且 此时 dis[2]是可抵达的。
为什么第一轮松弛操作无法松弛dis[3], 而第二次轮操作却成功松弛呢 ?
因为经过第一轮松弛操作 dis[2] 已经改变了,已经可抵达了,缩小了,松弛成功了。
换句话说 : 经过第一轮松弛,我们就找到了源点到其他顶点经过一条边最短路。 经过第二轮松弛, 我们就找到了源点到其他顶点经过两个条边的最短路。 那么经过多少轮松弛才可以得到源点到其余顶点的最短路呢 ?
应该是经过 (顶点数 - 1 )轮松弛,就可以找到其余所有顶点的最短路。(这里需要多思考,大家可以手动模拟一下)
- #include<iostream>
- #include<cstring>
- using namespace std;
-
- const int N = 100, M = 100;
-
- //读入点数 和 边数
- int n, m;
- //dis数组, 记录上次状态的dis数组
- int dis[N];
-
- //存储边的结构体数组
- struct Edge {
- int a, b, w;
- }edges[M];
-
- void bellmanford() {
- //初始化dist数组
- memset(dis, 0x3f, sizeof(dis));
- dis[1] = 0;// 1是源点
-
- //经过 n - 1次松驰
- //对所有边进行一次松弛操作,就求出了源点到所有点,经过的边数最多为1的最短路
- //对所有边进行两次松弛操作,就求出了源点到所有点,经过的边数最多为2的最短路
- //....
- //对所有边进行n- 1次松弛操作,就求出了源点到所有点,经过的边数最多为n - 1的最短路
- for(int i = 0; i < n - 1; i++) {
-
- //遍历所有边
- for(int j = 0; j < m; j++) {
- int a = edges[j].a, b = edges[j].b, w = edges[j].w;
- if(dis[a] != 0x3f3f3f3f && dis[b] > dis[a] + w) //松弛操作
- dis[b] = dis[a] + w;
- }
- }
-
- }
- int main() {
- //读入点数,边数
- cin >> n >> m;
- //读入边
- for(int i = 0; i < m; i++) {
- int a, b, w;
- cin >> a >> b >> w;
- edges[i] = {a, b, w};
- }
-
- //调用 bellman - ford算法
- bellmanford();
-
- //打印dis数组
- for(int i = 1; i <= n; i++)
- cout << dis[i] << " ";
- cout << endl;
-
- system("pause");
- return 0;
- }
- /*
- 输出样例
- 5 5
- 2 3 2
- 1 2 -3
- 1 5 5
- 4 5 2
- 3 4 3
- 输出样例
- 0 -3 -1 2 4
- */

1. bellman-ford是可以进行优化的,首先不一定进行 n - 1轮松弛操作才会求出最短路。也许再 n - 3轮的时候就求出了。而且每次松弛操作,不一定成功。比如 2 - > 3 权值为2这条边。我们在第二轮才松弛了 dis[3] , 因为只有松弛了dis[2]才能松弛dis[3] :)。所以我们可以用队列记录被松弛顶点,然后通过该顶点来松弛其他相邻顶点。这就是SPFA(Shortest Path Fast Algorithm)算法。读者可以自己实现一下哦。SPFA的最差时间复杂度是O(NM),但是正常情况下很快的。
2.bellman-ford算法可以检测负权环。正常情况,最差 n - 1次松弛 就可以求出最短路。但是如果存在负权环,是没有最短路的,我们可以通过反复走这条边,来缩短距离。如果要检测负权环,我们只需要在bellman-ford运行完成后,再进行一轮松弛操作。如果松弛操作成功,那么证明有负权环。
3.最后希望大家变得更强:)。如文章有错误,烦请指出~
参考资料
《啊哈算法》
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。