source: proiecte/pgraph/Code/Dijkstra/dijkstra2.c @ 129

//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define inf 50000001


int main()
{
        int d[10005],min,**mat,i,j,n,nod;
        char viz[10005];
        clock_t start,stop;
        FILE *f=fopen("dijkstra.in","r");

        fscanf(f,"%i",&n);
        mat=(int **) calloc(n*n,sizeof(int *));
        for(i=0;i<n;i++)
                mat[i]=(int *) calloc(n,sizeof(int));

        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        fscanf(f,"%i",&mat[i][j]);
        fclose(f);

        memset(viz,0,sizeof(viz));
        start=clock();
        d[0]=0;
        for(i=1;i<n;i++)
                d[i]=inf;

        for(;;)
        {
                min=inf;
                for(i=0;i<n;i++)
                {
                        if(viz[i]==0 && d[i]<min)
                        {
                                min=d[i];
                                nod=i;
                        }
                }
                if(min==inf)
                        break;
                viz[nod]=1;

                for(i=0;i<n;i++)
                {
                        if(mat[nod][i]+d[nod]<d[i] && mat[nod][i]!=-1)
                                d[i]=mat[nod][i]+d[nod];
                }
        }
        stop=clock();
        printf("Au trecut %f secunde",(double)(stop-start)/CLOCKS_PER_SEC);

        f=fopen("dijkstra.out","w");
        for(i=1;i<n;i++)
        {
                if(d[i]==inf)
                        d[i]=0;
                fprintf(f,"%i ",d[i]);
        }
        fprintf(f,"%s","\n");
        fclose(f);
        for(i=0;i<n;i++)
                free(mat[i]);
        free(mat);
        return 0;
}