floyd_warshall.c

用C语言实现最短路径算法中的Floyd-Warshall算法

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

#define SIZE 8

int r[SIZE+1][SIZE][SIZE];

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

	fpin=fopen("E:\\learn vc\\floyd_warshall\\distance_2.txt","r");
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++)
			fscanf(fpin,"%d\n",&r[0][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 floyd_warshall()
{
	FILE *fpout;
	int v,u,k;
	int sum;

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

void main()
{
	readin();
	floyd_warshall();
	exit(0);
}