/* 標準文檔模板 */

#include "Stdio.h"
#include "Conio.h"
#define N 5        /*N為結點總數*/
int main(void)
{
   int dis[N]; int path[N]; int k=0,i,mark,max,a,j;int b[N];
 int q[100];int z; int M[N][N];


   FILE *fp;
    fp=fopen("data.txt","r");
    for(i=0;i<N;i++)
      for(j=0;j<N;j++)
       {fscanf(fp,"%d",&M[i][j]);}
    fclose(fp);




 for(i=0;i<N;i++)        /*設定k源點，path，dis的初值*/
 { if(i!=k) M[i][i]=0;        /*k為源點*/
   else M[i][i]=1;
   dis[i]=M[k][i];  /*源點到個頂點路徑長度*/
   if(dis[i]<32767) path[i]=k;
   else path[i]=0;
  }

 for(i=0;i<N-1;i++)     /*確定源點到各頂點路徑，除源點外要處理N-2條路徑*/
 { mark=k; max=32767;
   for(a=0;a<N;a++)    /*在未處理的頂點中，確定當前路徑中最短路徑*/
    {  if(M[a][a]==0&&dis[a]<max)
         {max=dis[a];mark=a;}
     }

 /*  printf("mark=%d",mark);printf("\n");  */

                      /*mark，max中記錄路徑最短的結點下標和長度*/
       /*所有結點處理完畢，結束*/
    M[mark][mark]=1;     /*將選中頂點送入w集合中*/

   for(j=0;j<N;j++)      /*利用頂點mark調整dis中路徑長度*/
    { if(M[j][j]==0&&M[mark][j]<32767&&dis[mark]+M[mark][j]<dis[j])
        {dis[j]=dis[mark]+M[mark][j]; /*  printf("dis[%d]=%d ",j,dis[j]);printf("\n"); */
          path[j]=mark;  /*調整j結點的直接前驅*/
         }
     }
  }

for(i=0;i<N;i++)
 {if(i==k||dis[i]==0)continue;
  printf("%d-%d: ",k,i);
  q[0]=path[i];
  j=0;

  while(q[j]!=k)
  {j++;
   q[j]=path[q[j-1]];

  }

   for(z=j;z>=0;z--)
   { printf("%d-",q[z]);
    }printf("%d",i); printf("    "); printf("dis=%d",dis[i]);   printf("\n");

 }
getch();

}