//s is the membership array for the solution set
//f is that for the frontier set
//array p is to keep track of the predecessor of w
//When the distance to w is updated or set up, we 
//perform p[w]=v. At the end, we traverse the array p
//until we hit 0. This sequence will give us the shortest
//path in reverse order, so we output the shortest path
//from array path in reverse order to get the correct order.
#include <stdio.h>
main(argc,argv)
int argc;
char *argv[];
{
int i,j,k,n,v,w,so;
int d[100],f[100],s[100], p[100], path[100];
int a[100][100];
FILE *in_file;
  in_file=fopen(*++argv,"r"); 
  fscanf(in_file,"%d\n",&n);
  printf("n= %d \n", n);
    fscanf(in_file, "\n");
  for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) fscanf(in_file, "%d ",&a[i][j]);
    fscanf(in_file, "\n");
  };
  for (i=1;i<=n;i++){
    for (j=1;j<=n;j++) printf("%4d ",a[i][j]);
    printf("\n");
  }
  printf("Input source ");
  scanf("%d", &so);  /* so is the source */
  for (j=1;j<=n;j++){
    d[j]=a[so][j]; s[j]=0; f[j]=0;
  }; 
  for (i=1;i<=n;i++)printf("%d ",d[i]); printf("\n");
  p[so]=0;
  f[so]=1;
  getchar();
  d[0]=99;  
  for (j=1;j<=n;j++){ 
    v=0; 
    for (w=1;w<=n;w++) 
      if (f[w]==1) if (d[w]<d[v]) v=w;
    s[v]=1; f[v]=0;
    printf("%d selected\n",v);
    for (w=1;w<=n;w++)  if (a[v][w]<99) 
      if (s[w]==0){ 
        if (f[w]==1){   
          if (d[v]+a[v][w]<d[w]) {
            d[w]=d[v]+a[v][w];
            p[w]=v;  /* v is the predecessor of w */
          }
        }
        else { 
          d[w]=d[v]+a[v][w];
          f[w]=1;
          p[w]=v;  /* v is the predecessor of w */
        }
      }
      printf("frontier     ");
      for (w=1;w<=n;w++) printf("%d ",f[w]); printf("\n");
      printf("solution set ");
	  for (w=1;w<=n;w++)printf("%d ",s[w]); printf("\n");
	  printf("  d=  ");
      for (w=1;w<=n;w++) printf("%d ", d[w]); getchar();
      printf("\n");
  };
  printf("Input destination ");
  scanf("%d", &w);
  i=0; 
  while (w!=0) {i++; path[i]=w; w=p[w];} /* Store the path in path */
  for (i=i;i>=1;i--)printf("%d ",path[i]); /* Output path in reverse order */
  printf("\n");
}