dijkstra.cpp

The math to find out the short line by Djikstra algorithm

//Giai thuat tham lam
// Thuat toan Dijkstra
// Tim duong di ngan nhat
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define filein "Dijkstra.inp"
#define fileout "Dijkstra.out"
#define NMAX 100
#define MAX 10000
int n,s,t;
int c[NMAX][NMAX];
int Previous[NMAX];
int Free[NMAX];
int d[NMAX];
void Input_Data()                       //nap vao duong di cua do thi
{
    int i,j;
    FILE *fp;
    fp=fopen(filein,"r");
    fscanf(fp,"%d%d%d",&n,&s,&t);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            fscanf(fp,"%d",&c[i][j]);
            if(c[i][j]==0)
                c[i][j]=MAX;
        }
    }
    fclose(fp);
}
// Khoi tao cac gia tri dau
void Init()
{
    int v;
    for(v=1;v<=n;v++)
    {
        d[v]=c[s][v];
        Previous[v]=s;
        Free[v]=1;
    }
    Previous[s]=0;
    d[s]=0;
    Free[s]=0;
}
void Dijkstra()
{
    int u,v,minp;
    while(Free[t])
    {
        minp=MAX;
        // Lay trong tap v ra dinh u chua danh dau co d[v] min
        for(v=1;v<=n;v++)
        {
            if(Free[v] && (minp>d[v]))
            {
                minp=d[v];
                u=v;
            }
        }
        // Co dinh u
        Free[u]=0;     //xoa u ra khoi tap Free[t]
        if(Free[t])        //voi dinh t con trong tap Free
        {
            for(v=1;v<=n;v++)
            {
                if(Free[v] && (d[u]+c[u][v]<d[v])) // voi dinh u ke voi v
                {
                    d[v]=d[u]+c[u][v];    // chon duong di ngan nhat tu toi v
                    // Luu vet
                    Previous[v]=u; //Danh nhan lai cho dinh u
                }
            }
        }
    }
}
void Output_Data()
{
    int i;
    FILE *fp;
    fp=fopen(fileout,"w");
    fprintf(fp,"+ Duong di ngan nhat tu %d den %d la :\n",s,t);
    fprintf(fp,"%d<--",t);
    i=Previous[t];
    while(i!=s)
    {
        fprintf(fp,"%d<--",i);
        i=Previous[i];
    }
    fprintf(fp,"%d",s);
    fprintf(fp,"\n+ Do dai duong di ngan nhat la :%d",d[t]);
    fclose(fp);
}
int main()
{
    // Nhap du lieu
    Input_Data();
    // Initialize app
    Init();
    // Dijkstra
    Dijkstra();
    // Xuat du lieu
    Output_Data();
    return 0;
}