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