/* 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;
}