C++ Bellman-Ford算法
算法特点：
1 可求负边权 2 单源最短路 3 顶点数x边数 最好小于1000000 4 少量数据结构基础和一点点的算法基础
Bellman-Ford 算法可以在最短路存在的情况下求出最短路，并且能够判断图中是否存在负边权。算法是基于这样一个故事：一个图的最短路径如果存在，那么最短路径中必定不存在负权圈，所以最短路的顶点数除了起点外最多只有n-1个点。
算法原理：算法同样利用了最短路的最优子结构性质，用d[i]表示起点s到i的最短路，那么边数上限为j的最短路可以通过边数上限为j-1的最短路加入一条边得到，通过n-1次迭代，最后求得s到所有点的最短路。
算法描述：
对于图 G = ，源点为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 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 >> e; for(int i=0; i> c[i]; } c[n-1] = 0; m = 0; for(int i=0; i> 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 #include 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 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> str[i]; } for(int i=0; i<n; ++i){ for(int j = i+1; j> 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 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 >> m >> x; --x; for(int i=0; i> 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;}
