1 #include<stdio.h>
2 #define max 0xffffff
3 int g[20001][20001]; //图的邻接矩阵
4 int dist[20001];
5 int n;//顶点个数
6 int m;//边个数
7 struct Edge
8 {
9 int u, v, w; //边：起点、终点、权值
10 };
11 Edge e[200001];
12 bool bellman_ford(int n)//bellman-ford算法
13 {
14 int i, k, t,j;
15 for(i=0;i<n;i++)
16 dist[i]=g[0][i];//初始化
17 for(i=1;i<=n-1;i++)
18 {
19
20 /*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的
21 最短距离缩短,即判断dist[edges[k].u] + edges[k].w < dist[edges[k].v] 是否成立*/
22 for(j=0;j<n;j++)
23 {
24 printf("%d ",dist[j]);
25 }
26 printf("\n");
27 for(k=1;k<=m;k++)
28 {
29 t=dist[e[k].u]+e[k].w;
30 if(dist[e[k].u]<max&&t<dist[e[k].v])
31 {
32 dist[e[k].v] = t;
33 }
34 }
35 }
36 /*以下是检查，若还有更新则说明存在无限循环的负值回路*/
37 for(k = 0; k < m; k ++)
38 {
39 if(dist[e[k].u] != max &&dist[e[k].u] + e[k].w < dist[e[k].v])
40 {
41 return false;
42 }
43 }
44 return true;
45 }
46
47 int main()
48 {
49 scanf("%d %d",&n,&m);
50 int i,j;
51 for(i=0;i<n;i++)
52 {
53 for(j=0;j<n;j++)
54 g[i][j]=max;
55 g[i][i]=0;
56 }
57 for(i=1;i<=m;i++)
58 {
59 int a,b,c;
60 scanf("%d %d %d",&a,&b,&c);
61 e[i].u=a;
62 e[i].v=b;
63 e[i].w=c;
64 g[a][b]=c;
65 }
66 for(i=0;i<n;i++)
67 {
68 for(j=0;j<n;j++)
69 printf("%d ",g[i][j]);
70 printf("\n");
71 }
72 bellman_ford(n);
73 for(i=0;i<n;i++)
74 {
75 printf("%d\n",dist[i]);
76 }
77
78 return 0;
79 }
80
81
82
83 /*
84
85 7 10
86 0 1 6
87 0 2 5
88 0 3 5
89 1 4 -1
90 2 1 -2
91 2 4 1
92 3 2 -2
93 3 5 -1
94 4 6 3
95 5 6 3
96
97 Press any key to continue
98
99
100 */
Bellman-Ford算法：
为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。
Bellman-Ford算法思想
Bellman-Ford算法构造一个最短路径长度数组序列dist 1 [u], dist
2 [u], …, dist n-1 [u]。其中：
vdist 1
[u]为从源点v到终点u的只经过一条边的最短路径长度，并有dist 1 [u] =Edge[v][u]；
vdist 2
[u]为从源点v最多经过两条边到达终点u的最短路径长度；
vdist 3
[u]为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度；
……
vdist n-1
[u]为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度；
算法的最终目的是计算出dist n-1
[u]，为源点v到顶点u的最短路径长度。
ü采用递推方式计算 dist k [u]。
v设已经求出 dist k-1 [u] , u = 0, 1, …,
n-1，此即从源点v最多经过不构成负权值回路的k-1条边到达终点u的最短路径的长度。
v从图的邻接矩阵可以找到各个顶点j到达顶点u的距离Edge[j][u]，计算min{ dist k-1 [j] +
Edge[j][u] } ，可得从源点v绕过各个顶点，最多经过不构成负权值回路的k条边到达终点u的最短路径的长度。
v比较dist k-1 [u]和min{ dist k-1 [j] + Edge[j][u] } ，取较小者作为dist k
[u]的值。
递推公式(求顶点u到源点v的最短路径)：
dist 1 [u] = Edge[v][u]
dist k [u] = min{ dist k-1 [u], min{ dist k-1 [j] + Edge[j][u] } }, j=0,1,…,n-1,j≠u
struct Edge { int u, v, w; //边：起点、终点、权值 }; Edge e[10001]; void bellman_ford(int n)//bellman-ford算法 { int i, k, t; for(i=1;i<=n;i++) dist[i]=g[1][i];//初始化 for(i=2;i<=n;i++) { for(k=1;k<=m;k++) { t=dist[e[k].u]+e[k].w; if(dist[e[k].u]<max&&t<dist[e[k].v]) { dist[e[k].v] = t; } } } }
代码实现：
View Code
1 #include<stdio.h> 2 #define max 0xffffff 3 int g[20001][20001]; //图的邻接矩阵 4 int dist[20001]; 5 int n;//顶点个数 6 int m;//边个数 7 struct Edge 8 { 9 int u, v, w; //边：起点、终点、权值 10 }; 11 Edge e[200001]; 12 bool bellman_ford(int n)//bellman-ford算法 13 { 14 int i, k, t,j; 15 for(i=0;i<n;i++) 16 dist[i]=g[0][i];//初始化 17 for(i=1;i<=n-1;i++) 18 { 19 20 /*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的 21 最短距离缩短,即判断dist[edges[k].u] + edges[k].w < dist[edges[k].v] 是否成立*/ 22 for(j=0;j<n;j++) 23 { 24 printf("%d ",dist[j]); 25 } 26 printf("\n"); 27 for(k=1;k<=m;k++) 28 { 29 t=dist[e[k].u]+e[k].w; 30 if(dist[e[k].u]<max&&t<dist[e[k].v]) 31 { 32 dist[e[k].v] = t; 33 } 34 } 35 } 36 /*以下是检查，若还有更新则说明存在无限循环的负值回路*/ 37 for(k = 0; k < m; k ++) 38 { 39 if(dist[e[k].u] != max &&dist[e[k].u] + e[k].w < dist[e[k].v]) 40 { 41 return false; 42 } 43 } 44 return true; 45 } 46 47 int main() 48 { 49 scanf("%d %d",&n,&m); 50 int i,j; 51 for(i=0;i<n;i++) 52 { 53 for(j=0;j<n;j++) 54 g[i][j]=max; 55 g[i][i]=0; 56 } 57 for(i=1;i<=m;i++) 58 { 59 int a,b,c; 60 scanf("%d %d %d",&a,&b,&c); 61 e[i].u=a; 62 e[i].v=b; 63 e[i].w=c; 64 g[a][b]=c; 65 } 66 for(i=0;i<n;i++) 67 { 68 for(j=0;j<n;j++) 69 printf("%d ",g[i][j]); 70 printf("\n"); 71 } 72 bellman_ford(n); 73 for(i=0;i<n;i++) 74 { 75 printf("%d\n",dist[i]); 76 } 77 78 return 0; 79 } 80 81 82 83 /* 84 85 7 10 86 0 1 6 87 0 2 5 88 0 3 5 89 1 4 -1 90 2 1 -2 91 2 4 1 92 3 2 -2 93 3 5 -1 94 4 6 3 95 5 6 3 96 97 Press any key to continue 98 99 100 */