首页 > 代码库 > Bellman-Ford——解决负权边
Bellman-Ford——解决负权边
Dijkstra算法虽好,但是不能解决带负权边的图,而Bellman-Ford就是解决这个问题的
在一个含有n个顶点的图中,任意两点之间的最短路径最多包含n-1条边,最短路径中不可能包含回路.
最短路径是一个不包含回路的简单路径,回路分为正权回路(回路权值之和为正)和负权回路(回路权值之和为负). 如果最短路径中包含正权回路,那么去掉这个回路,一定可以得到更短的路径;如果最短路径中包含负权回路,那么肯定没有最短路径,因为每多走一次负权回路就可以得到更短的路径. 因此最短路径肯定是一个不包含回路的最短路径,即最多包含n-1条边.
Code:
#include <stdio.h> #include <string.h> #include <stdlib.h> #define INF 999999 int main(int argc, char const *argv[]) { int i, j, n, m; int dis[10], temp[10], u[10], v[10], w[10]; int check, flag = 0; scanf("%d %d", &n, &m); for(i = 1; i <= m; ++i) { scanf("%d %d %d", &u[i], &v[i], &w[i]); } for(i = 1; i <= n; ++i) { dis[i] = INF; } dis[1] = 0; /// for(j = 1; j < n; ++j) /// 最多循环n-1次 { for(i = 1; i <= n; ++i) { temp[i] = dis[i]; /// 对BellmanFord优化,有可能在n-1轮松弛之前就已经计算出最短路径,所以先备份dis数组 } for(i = 1; i <= m; ++i) /// 最核心的3句Bellman-Ford算法 { if(dis[v[i]] > dis[u[i]] + w[i]) { dis[v[i]] = dis[u[i]] + w[i]; } } check = 0; /// 检测dis数组是否有更新 for(i = 1; i <= n; ++i) { if(temp[i] != dis[i]) { check = 1; break; } } if(!check) /// 没有更新则提前退出程序 { break; } } for(i = 1; i <= m; ++i) /// n-1次之后最短路径还会发生变化则含有负权回路 { if(dis[v[i]] > dis[u[i]] + w[i]) { flag = 1; } } if(flag) { printf("负权回路"); } else { for(i = 1; i <= n; ++i) { printf("%d ", dis[i]); } } printf("\n"); system("pause"); return 0; }
Bellman-Ford——解决负权边
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。