#include<stdio.h>
#define max 0xffffff
int g[][]; //图的邻接矩阵
int dist[];
int n;//顶点个数
int m;//边个数
struct Edge
{
int u, v, w; //边：起点、终点、权值
};
Edge e[];
bool bellman_ford(int n)//bellman-ford算法
{
int i, k, t,j;
for(i=;i<n;i++)
dist[i]=g[][i];//初始化
for(i=;i<=n-;i++)
{ /*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的
最短距离缩短,即判断dist[edges[k].u] + edges[k].w < dist[edges[k].v] 是否成立*/
for(j=;j<n;j++)
{
printf("%d ",dist[j]);
}
printf("\n");
for(k=;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;
}
}
}
/*以下是检查，若还有更新则说明存在无限循环的负值回路*/
for(k = ; k < m; k ++)
{
if(dist[e[k].u] != max &&dist[e[k].u] + e[k].w < dist[e[k].v])
{
return false;
}
}
return true;
} int main()
{
scanf("%d %d",&n,&m);
int i,j;
for(i=;i<n;i++)
{
for(j=;j<n;j++)
g[i][j]=max;
g[i][i]=;
}
for(i=;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[i].u=a;
e[i].v=b;
e[i].w=c;
g[a][b]=c;
}
for(i=;i<n;i++)
{
for(j=;j<n;j++)
printf("%d ",g[i][j]);
printf("\n");
}
bellman_ford(n);
for(i=;i<n;i++)
{
printf("%d\n",dist[i]);
} return ;
} /* 7 10
0 1 6
0 2 5
0 3 5
1 4 -1
2 1 -2
2 4 1
3 2 -2
3 5 -1
4 6 3
5 6 3 Press any key to continue */
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[];
void bellman_ford(int n)//bellman-ford算法
{
int i, k, t;
for(i=;i<=n;i++)
dist[i]=g[][i];//初始化
for(i=;i<=n;i++)
{
for(k=;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;
}
}
}
}
代码实现：0(v*e)
#include<stdio.h>
#define max 0xffffff
int g[][]; //图的邻接矩阵
int dist[];
int n;//顶点个数
int m;//边个数
struct Edge
{
int u, v, w; //边：起点、终点、权值
};
Edge e[];
bool bellman_ford(int n)//bellman-ford算法
{
int i, k, t,j;
for(i=;i<n;i++)
dist[i]=g[][i];//初始化
for(i=;i<=n-;i++)
{ /*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的
最短距离缩短,即判断dist[edges[k].u] + edges[k].w < dist[edges[k].v] 是否成立*/
for(j=;j<n;j++)
{
printf("%d ",dist[j]);
}
printf("\n");
for(k=;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;
}
}
}
/*以下是检查，若还有更新则说明存在无限循环的负值回路*/
for(k = ; k < m; k ++)
{
if(dist[e[k].u] != max &&dist[e[k].u] + e[k].w < dist[e[k].v])
{
return false;
}
}
return true;
} int main()
{
scanf("%d %d",&n,&m);
int i,j;
for(i=;i<n;i++)
{
for(j=;j<n;j++)
g[i][j]=max;
g[i][i]=;
}
for(i=;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[i].u=a;
e[i].v=b;
e[i].w=c;
g[a][b]=c;
}
for(i=;i<n;i++)
{
for(j=;j<n;j++)
printf("%d ",g[i][j]);
printf("\n");
}
bellman_ford(n);
for(i=;i<n;i++)
{
printf("%d\n",dist[i]);
} return ;
} /* 7 10
0 1 6
0 2 5
0 3 5
1 4 -1
2 1 -2
2 4 1
3 2 -2
3 5 -1
4 6 3
5 6 3 Press any key to continue */
0(n*n*n)
void bellman_ford(int n)//bellman-ford算法
{
int i, k, t,j;
for(i=;i<=n;i++)
dist[i]=g[][i];//初始化
for(k=;k<=n;k++)
{
for(j=;j<=n;j++)
{
for(i=;i<=n;i++)
{
if(g[i][j]<max&&dist[i]+g[i][j]<dist[j])
dist[j]=dist[i]+g[i][j];
}
}
}
}