bellman_ford.c

用C语言实现最短路径算法中的Bellman-Ford算法

#include "stdio.h"
#include "stdlib.h"

#define SIZE 14

int d[SIZE][SIZE];
int a[SIZE][SIZE-1][SIZE];

void readin()
{
	FILE *fpin;
	int i,j;

	fpin=fopen("E:\\learn vc\\bellman\\distance.txt","r");
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++)
			fscanf(fpin,"%d\n",&d[i][j]); 
	fclose(fpin);
}

int addnew(int a,int b)
{
	int c;

	if(a!=99999&&b!=99999)
		c=a+b;
	else
		c=99999;

	return(c);
}

void bellman_ford()
{
	FILE *fpout;
	int u,k,v,w;
	int sum;

	for(u=0;u<SIZE;u++)
	{
		for(k=0;k<SIZE-2;k++)
			for(v=0;v<SIZE;v++)
			{
				a[u][k+1][v]=a[u][k][v];
				for(w=0;w<SIZE;w++)
				{
					sum=addnew(a[u][k][w],d[w][v]);
					if(a[u][k+1][v]>sum)
						a[u][k+1][v]=sum;
				}
			}
		fpout=fopen("E:\\learn vc\\bellman\\bellman_ford.txt","w");
		for(v=0;v<SIZE;v++)
			for(w=0;w<SIZE;w++)
			{
				sum=addnew(a[u][SIZE-2][w],d[w][v]);
				if(a[u][SIZE-2][v]>sum)
				{
					fprintf(fpout,"False.\n");
					exit(0);
				}
			}
	}
	fprintf(fpout,"True.\n");
	for(u=0;u<SIZE;u++)
	{
		fprintf(fpout,"The node %d:\n",u);
		for(k=0;k<SIZE-1;k++)
		{
			fprintf(fpout,"k=%d:",k);
			for(v=0;v<SIZE;v++)
				fprintf(fpout,"%d,",a[u][k][v]);
			fprintf(fpout,"\n");
		}
	}
	fclose(fpout);
}

main()
{
	int i,j;

	readin();
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++)
			a[i][0][j]=d[i][j];
	bellman_ford();
}