Bellman-ford 代码实现

修改一次边称为一次松弛.

下面给出测试数据,第一行是顶点个数n,,然后输入每条边的数据,格式为u,v,w分别表示这条边的起点,终点和权值,顶点从0开始记起,最后一行为-1 -1 -1 ,表示数据输入的结束.

将数据保存为in.txt与源代码放在同一目录下.

/*we start 0 */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define INF 1000000
#define MAXN 10
int n;

int edge[MAXN][MAXN];
int dist[MAXN];
int path[MAXN];
/*Bellman algorithm hell
 * init the function 
 * here,the meaning of expression of dist[] and path[]
 * dist[] is distance ,path[2]=0 means vertex 0 to vertex 2 directed way the vertex 0 is fronter,else is -1  */
void Bellman(int v0)
{
	int i,j,k,u;//k是表示从源点到各点的线路条数,u就是从0到那个顶点
	for(i=0;i<n;i++)
	{
		dist[i]=edge[v0][i];//将第一个源点到各点的距离写入dist[i]
		if(i!=v0 && dist[i]<INF)//将与v0有直接关系的顶点的path值改写
			path[i]=v0;
		else
			/*其余各点为-1*/
			path[i]=-1;
	}
	/*从dist(1)[u]递推出dist(2)[u],dist(3)[u]....dist(n-1)[u]*/
	for(k=2;k<n;k++)
	{
		/*修改每个顶点的dist[u]和path[u]*/
		for(u=0;u<n;u++)
		{
			if(u!=v0)
			{
				/*考虑其他每个顶点*/
				for(j=0;j<n;j++)
				{
					/*顶点j到顶点u有直接路径....*/
					if(edge[j][u]<INF && dist[j]+edge[j][u]<dist[u])
					{
						/*这一步称为松弛:Slack,to be honst,我不理解
						 * 课本上这样说:Bellman-ford的算法的本质是对
						 * 每条边进行判断,设边的权值为w(j,u),在这里
						 * 就是edge[j][u],如果边w(j,u)的引入会使得
						 * dist`[u]的值减小即将dist[j]+edge[j][u]赋给dist[u]
						 * ,那么前一句
						 * edge[j][u]<INF
						 * 就是
						 * 说可以引入边w(j,u)*/
						dist[u]=dist[j]+edge[j][u];
						path[u]=j;
					}
				}

			}
		}
	}

}
int main()
{
	freopen("in.txt","r",stdin);
	int u,v,w,i,j;
	cin>>n;
	//	memset(edge,0,sizeof(edge));
		while(1)
		{
			scanf("%d%d%d",&u,&v,&w);
			if(u==-1 && v==-1 && w==-1)
				break;
			edge[u][v]=w;
		}
			for(i=0;i<n;i++)
				for(j=0;j<n;j++)
				{
					if(i==j)
						edge[i][j]=0;
					else if(edge[i][j]==0)
						edge[i][j]=INF;


				}

			Bellman(0);
			int shortest[MAXN];
			/*在这里运用了倒向追踪的方法,That‘s what?*/
			for(i=1;i<n;i++)
			{
				printf("%d\t",dist[i]);//输出各顶点时存放的序号
				memset(shortest,0,sizeof(shortest));
				int k=0;//
				shortest[k]=i;
				while(path[shortest[k]]!=0)
				{
					k++;
					shortest[k]=path[shortest[k-1]];
				}
				k++;
				shortest[k]=0;
				for(j=k;j>0;j--)
					printf("%d-->",shortest[j]);
				printf("%d\n",shortest[0]);

			}
		
		return 0;
		
}

7
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
-1 -1 -1

运行结果如下:

Bellman-ford 代码实现,布布扣,bubuko.com

Bellman-ford 代码实现

原文：http://blog.csdn.net/yuzibo747/article/details/20391335