/* CHUONG TRINH MO TA THUAT TOAN DIJSTRA TIM DUONG DI NGAN NHAT TRONG DO THI.
* code by YoYoLove From FAMILUG - Girlxitin.com
* file dau vao: in.txt phai tao cung folder chua source, chua ma tran khoang cach
* gia tri vo cung duoc gan bang 999
* vi du:
0 1 2 3 999 999 999 999
1 0 1 999 5 999 999 999
2 1 0 1 999 1 999 999
3 999 1 0 999 999 2 999
999 5 999 999 0 2 999 1
999 999 1 999 2 0 1 3
999 999 999 2 999 1 0 1
999 999 999 999 1 3 1 0
*/
#include <stdio.h>
#define MAX 8 //so dinh cua ma traN
const INFINITE=999; // gia tri thay the cho gia tri vo cung
int matrix[MAX][MAX]; //tao ma tran khoang cach
int a=0, b=0, num=0; //tao bien toan cuc
int allselected(int *selected)
{
int i;
for(i=0;i<MAX;i++)
if(selected[i]==0)
return 0;
return 1;
}
void dijstra(int matrix[][MAX],int *preced,int *distance) //ham dijstra
{
int selected[MAX]={0};
int current=0,i,k,dc,smalldist,newdist;
for(i=0;i<MAX;i++)
{
distance[i]=INFINITE; // gan g.tri vo cung
}
selected[current]=1; //chon dinh dau la 1
distance[0]=0; // khoang cac tu dinh 1->1 la 0
current=0; //gan nhan 0 cho dinh 1
while(!allselected(selected))
{
smalldist=INFINITE; //khoang cach nho nhat
dc=distance[current];
for(i=0;i<MAX;i++) //bat dau thuat toan dijstra
{
if(selected[i]==0)
{
newdist=dc+matrix[current][i]; //khoang cach moi
if(newdist<distance[i])
{
distance[i]=newdist;
preced[i]=current;
}
if(distance[i]<smalldist)
{
smalldist=distance[i];
k=i;
}
}
} //ket thuc thuat toan dijstra
current=k;
selected[current]=1;
}
}
void creat_distmatrix() //ham tao ma tran khoang cach
{
printf("\n Nhap ma tran khoang cach");
for(a=0;a<MAX;a++)
{
printf("\n hang i = %d: ",a+1);
for(b=0;b<MAX;b++)
{
printf("\n gia tri cua hang %d cot %d: ",a+1,b+1);
scanf("%d", &num);
matrix[a][b]=num;
}
}
}
int main()
{
int choose;
FILE *of, *inf; //tao con tro tep
printf("\n Lua chon cach nhap du lieu...................................... ");
printf("\n Nhap tu ban phim chon 0 - nhap tu file chon 1, xong an Enter :..");
scanf("%d", &choose);
if(choose==0)
{
creat_distmatrix();
}
if(choose==1)
{
of=fopen("in.txt","r"); //mo tep in.txt de doc thong tin
if(of==NULL) // neu tep khong ton tai
{
printf("\n Qua tirnh nhap du lieu loi do tap tin khong ton tai... Enter de ket thuc");
}
else //neu tep ton tai
{
for(a=0;a<MAX;a++)
{
for(b=0;b<MAX;b++)
{
fscanf(of,"%d", &num); //gan cac phan tu trong tep vao "num"
matrix[a][b]=num; // Ghi tri cua "num" vao ma tran
}
}
}
}
if(of!=NULL) //neu tep ton tai
{
//hien thi ma tran
printf("\n Ma tran da nhap: \n");
for(a=0;a<MAX;a++)
{
for(b=0;b<MAX;b++)
{
printf(" %3d", matrix[a][b]);
}
printf("\n");
}
//tinh toan ket qua cua thuat toan
int i,preced[MAX]={0},distance[MAX];
dijstra(matrix,preced,distance);
//in ket qua tren man hinh
printf("\n Thu tu gan nhan cho cac dinh: ");
for(i=0;i<MAX;i++)
{
printf("\n Dinh %d: ",i+1);
printf("%d\n",distance[i]);
}
printf("\n Nhan cua dinh cuoi: %d", distance[MAX-1]);
//in ra file out.txt
inf=fopen("out.txt","w");
fprintf(inf,"\n Thu tu gan nhan cho cac dinh: ");
for(i=0;i<MAX;i++)
{
fprintf(inf,"\n Dinh %d: ",i+1);
fprintf(inf,"%d\n",distance[i]);
}
fprintf(inf,"\n Nhan cua dinh cuoi: %d", distance[MAX-1]);
fclose(of);
fclose(inf);
}
return 0;
}