当前位置：首页 > ai >正文

C++ Bellman-Ford算法

ai 2025/9/2 16:28:48

算法特点：

1 可求负边权 2 单源最短路 3 顶点数x边数最好小于1000000 4 少量数据结构基础和一点点的算法基础

Bellman-Ford 算法可以在最短路存在的情况下求出最短路，并且能够判断图中是否存在负边权。算法是基于这样一个故事：一个图的最短路径如果存在，那么最短路径中必定不存在负权圈，所以最短路的顶点数除了起点外最多只有n-1个点。

算法原理：算法同样利用了最短路的最优子结构性质，用d[i]表示起点s到i的最短路，那么边数上限为j的最短路可以通过边数上限为j-1的最短路加入一条边得到，通过n-1次迭代，最后求得s到所有点的最短路。

算法描述：

对于图 G = <V, E>，源点为s，d[i]表示s到i的最短路

1 初始化所有顶点d[i] = inf，令d[s] = 0, 计数器等于 c = 0

2 枚举每条边w(u ,v) ，如果d[u] != inf ，则更新d[v] = min(d[v], d[u] + w(u, v))

3 计数器c自增1，当c== n-1时算法结束，否则重复步骤2。

这个算法并没有考虑负权圈的问题，如果存在负权圈的话，那么第二步操作的更新就会没有止境，所以判定负权圈的算法就出来了，只需要在第n次继续进行第二步的松弛操作，如果至少有一条边被更新，则肯定存在负权圈。

代码分析：

第一步定义边结构，Edge(u, v, w)

第二步边的添加，

function addEdge(edges, u, v, w)

edges.append(Edge(u, v, w));

第三步建图

addEdge(edges, u1, v1, w1);

addEdge(edges, u2, v2, w2);

...

第四步，实现松弛操作

function doRelax(edges, d[maxn])

isRelax = False

for i -> (0, edges.size()-1)

u, v, w = edges[i]

if d[u] + w < d[v]

d[v] = d[u] + w

isRelax = true;

return isRelax

算法核心

function bellman(n, s, edges, d[maxn])

for i -> (0, n-1)

d[i] = inf

d[s] = 0

for i -> (1, n-1)

if not doRelax(edges, d)

return false

return doRelax

时间复杂度，每次松弛操作都需要遍历所有的边，边数为m，最多遍历n次，所以总的时间复杂度为o(mn)

代码练习，对应蓝桥云课出差代码见下

#include <iostream>
using namespace std;#define maxn 1001
#define maxm 20001
#define eType int
#define inf 1000000000struct EDGE{int u, v;eType w;
};int doRelax(int m, EDGE* edges, eType* dist){int isRelax = 0;for(int i=0; i<m; ++i){int u = edges[i].u;int v = edges[i].v;eType w = edges[i].w;if(dist[u] + w < dist[v]){dist[v] = dist[u] + w;isRelax = 1;}}return isRelax;
}int bellman(int n, int m, EDGE* edges, int s, eType* dist){for(int i=0; i<n; ++i){dist[i] = (i == s ? 0:inf);}for(int i = 0; i<n-1; ++i){if(!doRelax(m, edges, dist)){return 0;}}return doRelax(m, edges, dist);
}int n, e, m;
EDGE edges[maxm];
eType dist[maxn];
int c[maxn];int main()
{cin >> n >> e;for(int i=0; i<n; ++i){cin >> c[i];}c[n-1] = 0;m = 0;for(int i=0; i<e; ++i){int u, v, w;cin >> u >> v >> w;edges[m].u = u - 1;edges[m].v = v - 1;edges[m].w = w + c[v - 1];m++;edges[m].u = v - 1;edges[m].v = u - 1;edges[m].w = w + c[u - 1];m++;}bellman(n, m, edges, 0, dist);cout << dist[n - 1] << endl;// 请在此输入您的代码return 0;
}

代码练习，对应蓝桥云课字母阶梯游戏，代码见下

#include <iostream>
#include <cstring>
using namespace std;#define maxn 1001
#define maxm 250001
#define eType int
#define inf 1000000000struct EDGE{int u, v;eType w;
};int doRelax(int m, EDGE* edges, eType* dist){int isRelax = 0;for(int i=0; i<m; ++i){int u = edges[i].u;int v = edges[i].v;eType w = edges[i].w;if(dist[u] + w < dist[v]){dist[v] = dist[u] + w;isRelax = 1;}}return isRelax;
}int bellman(int n, int m, EDGE* edges, int s, eType* dist){for(int i=0; i<n; ++i){dist[i] = (i == s ? 0:inf);}for(int i = 0; i<n-1; ++i){if(!doRelax(m, edges, dist)){return 0;}}return doRelax(m, edges, dist);
}int n, m;
EDGE edges[maxm];
eType dist[maxn];
int c[maxn];int calcEdge(char *a, char *b){int ans = 0;for(int i=0; a[i]; ++i){if(a[i] != b[i]){++ans;}if(ans > 1){return 0;}}return 1;
}char str[maxn][maxn];
char st[maxn], en[maxn];int main()
{cin >> n;m = 0;for(int i=0; i<n; ++i){cin >> str[i];}for(int i=0; i<n; ++i){for(int j = i+1; j<n; ++j){if (calcEdge(str[i], str[j])){edges[m].u = i;edges[m].v = j;edges[m].w = 1;m++;edges[m].u = j;edges[m].v = i;edges[m].w = 1;m++;}}}cin >> st;cin >> en;int s, d;for(int i=0; i<n; ++i){if(!strcmp(st, str[i])) s = i;if(!strcmp(en, str[i])) d = i;}bellman(n, m, edges, s, dist);if(dist[d] == inf) dist[d] = -1;cout << dist[d] << endl;// 请在此输入您的代码return 0;
}

代码练习，对应蓝桥云课小怂的黄牛派对代码见下

#include <iostream>
using namespace std;#define maxn 1001
#define maxm 100001
#define eType int
#define inf 1000000000struct EDGE{int u, v;eType w;
};int doRelax(int m, EDGE* edges, eType* dist){int isRelax = 0;for(int i=0; i<m; ++i){int u = edges[i].u;int v = edges[i].v;eType w = edges[i].w;if(dist[u] + w < dist[v]){dist[v] = dist[u] + w;isRelax = 1;}}return isRelax;
}int bellman(int n, int m, EDGE* edges, int s, eType* dist){for(int i=0; i<n; ++i){dist[i] = (i == s ? 0:inf);}for(int i = 0; i<n-1; ++i){if(!doRelax(m, edges, dist)){return 0;}}return doRelax(m, edges, dist);
}int n, m;
EDGE edges[maxm];
eType dist1[maxn], dist2[maxn];
int u[maxm], v[maxm], w[maxm];int main()
{int x;cin >> n >> m >> x;--x;for(int i=0; i<m; ++i){cin >> u[i] >> v[i] >> w[i];--u[i];--v[i];}for(int i=0; i<m; ++i){edges[i].u = u[i];edges[i].v = v[i];edges[i].w = w[i];}bellman(n, m, edges, x, dist1);for(int i=0; i<m; ++i){edges[i].u = v[i];edges[i].v = u[i];edges[i].w = w[i];}bellman(n, m, edges, x, dist2);int ret = 0;for(int i=0; i<n; ++i){ret = max(ret, dist1[i] + dist2[i]);}cout << ret << endl;// 请在此输入您的代码return 0;
}

查看全文

http://www.xdnf.cn/news/19516.html