Bellman-Ford算法模板
目录
Bellman-Ford
与 Dijkstra
算法一样,也是用于求带权图的最短路,不过与后者相比,前者可以解决边权为负数的情况,适应性较强;
算法主要的流程是对每一个点根据边进行松弛操作,最终求得最优解的过程。
算法的时间复杂度是O(V*E)
/*
* @Author : YaleXin
* @Email : me@yalexin.top
* @LastEditors : YaleXin
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 1501, MAX_M = 5e4 + 1, INF = 0x7f7f7f7f, START = 1;
int n, m, minD[MAX_N], pre[MAX_N];
struct Edge{
int u, v, w;
}edges[MAX_M];
// 快读
int read(){
int sum = 0;
bool ok = false;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')ok = true;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
sum = (sum << 1) + (sum << 3) + ch - '0';
ch = getchar();
}
return ok ? -sum : sum;
}
void dfs(int son){
if (son != pre[son]){
dfs(pre[son]);
cout << "->" << flush;
cout << son << flush;
} else{
cout << son << flush;
}
}
void print_path(int root) {
while (root != pre[root]) {
printf("%d-->", root);
root = pre[root];
}
if (root == pre[root]) printf("%d\n", root);
}
void print(){
for(int i = 1; i <= n; i++){
cout << "nodeId: " << i << ", minLen : " << minD[i] << ", path : " << ends;
dfs(i);
cout << endl;
}
}
// 不存在负环的时候,minD中保存的就是从起始点到各个点的最短路权值
bool Bellman_Ford(){
memset(minD, 0x7f, sizeof minD);
minD[START] = 0, pre[START] = START;
int u, v, w;
for(int i = 1; i < n; i++)
for(int j = 1; j <= m; j++){
u = edges[j].u, v = edges[j].v, w = edges[j].w;
if (minD[u] + w < minD[v]){
minD[v] = minD[u] + w;
pre[v] = u;
}
}
bool ok = true; //判断是否含有负权回路
for (int i = 1; i <= m; ++i)
if (minD[edges[i].v] > minD[edges[i].u] + edges[i].w) {
ok = false;
break;
}
return ok;
}
int main(){
n = read(), m = read();
int u, v, w;
for (int i = 1; i <= m; i++){
// 有向图
u = read(), v = read(), w = read();
edges[i].u = u, edges[i].v = v, edges[i].w = w;
}
if (Bellman_Ford()){
print();
} else{
cout << "not exit!" << endl;
}
return 0;
}
/*
5 7
1 2 5
1 3 5
2 5 -1
2 3 -2
3 4 3
3 5 -2
4 5 2
5 7
1 2 1
2 4 2
5 4 3
3 4 4
1 3 5
1 5 6
2 5 7
*/
这部分的代码尤为重要:
bool ok = true; //判断是否含有负权回路
for (int i = 1; i <= m; ++i)
if (minD[edges[i].v] > minD[edges[i].u] + edges[i].w) {
ok = false;
break;
}
如果存在从源点可达的权为负的回路,那么我就可以不断地通过使用这一条回路将路径长度缩小,即最小路径和不收敛,哪来的最短路?
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!
历史评论
开始评论