/*  DIJKSTRA'S ALGORITHM FOR FINDING THE SHORTEST PATHS FROM NODE 0  */
#define INFINITY 999
#define MAXNODE 20
#include "stdio.h"

int  D[MAXNODE], P[MAXNODE];
int  C[MAXNODE][MAXNODE], PATH[MAXNODE][MAXNODE];
int  VMS[MAXNODE];
int  n;   /*  # of nodes */
int  chose_w();
void update();

main()
{
int  i, j, w, cc;
FILE *fp;

/*  initialize the graph and data  */
for(i = 0; i < MAXNODE; i ++)
   for(j = 0; j < MAXNODE; j ++)
      C[i][j] = INFINITY;
for(i = 1; i < MAXNODE; i ++){
   D[i] = C[0][i];
   P[i] = 0;
   }
for(i = 1; i < MAXNODE; i ++)
   VMS[i] = 1;

/*  load graph */
n = 0;
fp = fopen("dijk1.dat","r");
while( !feof(fp) ){
   fscanf(fp, "%d %d %d", &i, &j, &cc);
   ( i > n ) ? (n = i):(n = n) ;
   ( j > n ) ? (n = j):(n = n) ;
   if( n > MAXNODE ){
      printf("\n Enter nodes error (max = %d) : ", MAXNODE);
      exit(0);
      }
   C[i][j] = cc;
   C[j][i] = cc;
   }
fclose(fp);
n ++;
printf( "The number of nodes = %d", n );

/*  initialize */
for(i = 1; i < n; i ++){
   D[i] = C[0][i];
   P[i] = 0;
   }
for(i = 1; i < n; i ++)
   VMS[i] = 1;

/*  begin search  */
for(j = 1; j < n; j ++){ /*  THIS PROCESS TAKE */
   w = chose_w();    
   update(w);
   }

/*  make paths */
for(i = 1; i < n; i ++){
   PATH[i][0] = 1;
   PATH[i][1] = i;
   j = P[i];
   while(j != 0 ){
      PATH[i][0] = PATH[i][0] + 1;
      PATH[i][PATH[i][0]] = j;
      j = P[j];
      }
   }

/*  output paths  */
for(i = 1; i < n; i ++){
   printf("\nD[%d] = %d  =>  ", i, D[i]);
   for(j = PATH[i][0]; j > 0; j --)
      printf("%d  ", PATH[i][j]);
   }

return( 1 );
}

int chose_w()
{
int  v, t, min_c;
min_c = INFINITY;
for(t = 1; t < n; t ++)
   if( VMS[t] )  /*  t in set V-S  */
      if( D[t] < min_c ){
  v = t;
  min_c = D[t];
  }
VMS[v] = 0;  /*  get v out of set V-S  */
return( v );
}

void update( v )
int  v;
{
int  t;
for(t = 1; t < n; t ++)
   if( VMS[t] )  /*  t in set V-S  */
      if( D[t] > D[v] + C[v][t] ){
  D[t] = D[v] + C[v][t];
  P[t] = v;
  }
}

/*  dijk1.dat
0 1 10
0 3 30
0 4 100
0 5 40
0 7 30
0 9 50
1 2 50
1 3 70
1 4 60
1 5 30
1 8 20
2 4 60
2 6 30
2 8 20
2 9 10
3 4 100
3 6 60
3 8 40
3 9 20
4 5 60
4 5 30
4 5 10
4 7 10
5 6 10
5 7 20
5 8 30
6 8 70
6 9 10
7 8 30
8 9 40
*/