Ford-Bellman

#include<process.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define N 100
#define VOCUC 32767

typedef struct
{
	int n;
	int a[N][N];
}GRAPH;


GRAPH g;
int previous[N+1][N]; // luu lai duong di ngan nhat
int mincost[N+1][N];		// do dai duong di tu i den j
int nhan[N]; //nhan kiem tra tinh lien thong
int soTPLT;
int step;

int x;


void doc(GRAPH &g)
{
	FILE *f;
	f=fopen("D:\\BELLMAN.txt","rt");
	if(f==NULL)
	{
		printf("Khong ton tai File BELLMAN \n");
		exit(0);
	}
	fscanf(f,"%d",&g.n);
	for(int i=0;i<g.n;i++)
	{
		for(int j=0;j<g.n;j++)
		{
			fscanf(f,"%d",&g.a[i][j]);
		}
	}

	fclose(f);
}

int kiemTRaVH(GRAPH g)// kiem tra tinh hop le cua do thi
{
	for(int i=0;i<g.n;i++)
		if(g.a[i][i]!=0)
			return 0;
	return 1;
}

int kt_huong(GRAPH g)
{
	for(int i=0;i<g.n;i++)
	{
		for(int j=0;j<g.n;j++)
			if(g.a[i][j]!=g.a[j][i])
				return 0;//la do thi co huong
	}
	return 1;//la do thi vo huong
}

void viSit(GRAPH g,int i,int labels)
{
	nhan[i]=labels;
	for(int j=0;j<g.n;j++)
		if(nhan[j]==0 && (g.a[i][j] != 0 || g.a[j][i]!=0))
			viSit(g,j,labels);
}

int xetLienThong(GRAPH g)
{
	for(int i=0; i<g.n; i++)
		nhan[i] = 0;
	soTPLT=0;
	for(i=0; i<g.n; i++)
		if(nhan[i] == 0)
		{
			soTPLT++;
			viSit(g,i,soTPLT);
		}
	if(soTPLT>1)
		return 0;
	return 1;
}

/*khoi tao cac thong so cho thuat toan*/
void Init(GRAPH g,int x)
{
	step =0;
	for(int i=0;i<g.n;i++)
	{
		mincost[step][i]=VOCUC;  //dung 32767 cho gia tri vo cuc
		previous[step][i]=i;
	}
	mincost[step][x]=0;
}

/* Thuat toan Bellman */
void Bellman(GRAPH g,int x)
{
	Init(g,x);
	int i;
	for(step=1;step<=g.n;step++)
	{
		for(int t=0;t<g.n;t++)
		{
			mincost[step][t]=mincost[step-1][t];
			previous[step][t]=previous[step-1][t];
		}
		for(i=0;i<g.n;i++)
		{
			//tim cac dinh j co duong noi tu j den i
			//va chi phi buoc step-1 cua j khac VOCUC
			for(int j=0;j<g.n;j++)
			{
				if(g.a[i][j]!=0 && mincost[step-1][i]!=VOCUC)
				{
					//cap nhat lai neu chi phi buoc step cua i la VOCUC
					//hoc chi phi di qua j: mincost[step-1][j]+ a[j][i] toi uu hon
					if(mincost[step][j]==VOCUC || mincost[step][j]>mincost[step-1][i]+g.a[i][j])
					{
						mincost[step][j]=mincost[step-1][i]+g.a[i][j];
						previous[step][j]=i;

					}
				}

			}
		}
		//so sanh mincost[step] voi mincost[step-1] neu bang nhau thi ket thuc
		int bSame = true;
		for( i=0;i<g.n;i++)
			if(mincost[step][i]!=mincost[step-1][i])
			{
				bSame=false;
				break;
			}
			if(bSame)
				break;
	}


}

void xuat(GRAPH g,int x)
{
	int z=0;
	int k=x,s;
	int t[N];
	if(kiemTRaVH(g)==0)
	{
		printf("do thi khong hop le\n");
		exit(0);
	}
	if(kt_huong(g)==1)
		printf("Day la do thi vo huong\n");
	else
		printf("day la do thi co huong\n");
	if(step==g.n+1)
	printf("do thi co chu trinh am\n");
	else
	{

		for( int i=0;i<g.n;i++)
		{
			if(xetLienThong(g)==0)
			{
				printf("do thi khong lien thong");
				break;
			}
			if(previous[step-1][i]==i || x==i ||previous[step-1][i]==VOCUC)
			printf("tu dinh %d->%d   khong co duong di\n",x,i);
			else
			{
				printf("tu dinh %d->%d   co do dai %d  ",x,i,mincost[step-1][i]);
				s=i;
				t[0]=i;
				z=1;
				do

				{
					t[z++]=previous[step][s];
					s=previous[step][s];
				}while(s!=x);

				printf("duong di:  ");
				for(int j=z-1;j>0;j--)
				printf("%d->",t[j]);
				printf("%d",t[0]);
				printf("\n");
			}
		}

	}
}

void xuatBellman(GRAPH g,int x)
{
	int z=0;
	int k=x,s;
	int t[N];
	FILE *f;
	f=fopen("D:\\BELLMAN_out.txt","wt");
	if(f==NULL)
	{
		fprintf(f,"khong ton tai file");
		exit(0);
	}
	fprintf(f,"Duong di ngan nhat bang thuat toan BELLMAN\n\n");
	if(kiemTRaVH(g)==0)
	{
		fprintf(f,"do thi khong hop le\n");
		exit(0);
	}
	if(kt_huong(g)==1)
		fprintf(f,"Day la do thi vo huong\n");
	else
		fprintf(f,"day la do thi co huong\n");
	if(step==g.n+1)
	fprintf(f,"do thi co chu trinh am\n");
	else
	{

		for( int i=0;i<g.n;i++)
		{
			if(xetLienThong(g)==0)
			{
				fprintf(f,"do thi khong lien thong => khong tim duoc duong di");
				break;
			}
			if(previous[step-1][i]==i || x==i||previous[step-1][i]==VOCUC)
			fprintf(f,"tu dinh %d->%d   khong co duong di\n",x,i);
			else
			{
				fprintf(f,"tu dinh %d->%d   co do dai %d  ",x,i,mincost[step-1][i]);
				s=i;
				t[0]=i;
				z=1;
				do

				{
					t[z++]=previous[step][s];
					s=previous[step][s];
				}while(s!=x);

				fprintf(f,"duong di:  ");
				for(int j=z-1;j>0;j--)
				fprintf(f,"%d->",t[j]);
				fprintf(f,"%d",t[0]);
				fprintf(f,"\n");
			}
		}

	}
	fclose(f);

}

void main()
{
	int x;
	doc(g);
	printf("nhap x: ");
	scanf("%d",&x);
	Bellman(g,x);
	xuat(g,x);
	xuatBellman(g,x);
}