// algo7-7.cpp 實現算法7.16的程序
 #define MAX_NAME 5 // 頂點字符串的最大長度+1
 #define MAX_INFO 20 // 相關信息字符串的最大長度+1
 typedef int VRType;
 typedef char VertexType[MAX_NAME];
 typedef char InfoType;
 #include"c1.h"
 #include"c7-1.h"
 #include"bo7-1.cpp"
 typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

 void ShortestPath_FLOYD(MGraph G,PathMatrix &P,DistancMatrix &D)
 { // 用Floyd算法求有向網G中各對頂點v和w之間的最短路徑P[v][w]及其
   // 帶權長度D[v][w]。若P[v][w][u]為TRUE,則u是從v到w當前求得最短
   // 路徑上的頂點。算法7.16
   int u,v,w,i;
   for(v=0;v<G.vexnum;v++) // 各對結點之間初始已知路徑及距離
     for(w=0;w<G.vexnum;w++)
     {
       D[v][w]=G.arcs[v][w].adj;
       for(u=0;u<G.vexnum;u++)
         P[v][w][u]=FALSE;
       if(D[v][w]<INFINITY) // 從v到w有直接路徑
       {
         P[v][w][v]=TRUE;
         P[v][w][w]=TRUE;
       }
     }
   for(u=0;u<G.vexnum;u++)
     for(v=0;v<G.vexnum;v++)
       for(w=0;w<G.vexnum;w++)
         if(D[v][u]+D[u][w]<D[v][w]) // 從v經u到w的一條路徑更短
         {
           D[v][w]=D[v][u]+D[u][w];
           for(i=0;i<G.vexnum;i++)
             P[v][w][i]=P[v][u][i]||P[u][w][i];
         }
 }

 void main()
 {
   MGraph g;
   int i,j,k,l,m,n;
   PathMatrix p;
   DistancMatrix d;
   CreateDN(g);
   for(i=0;i<g.vexnum;i++)
     g.arcs[i][i].adj=0; // ShortestPath_FLOYD()要求對角元素值為0
   printf("鄰接矩陣:\n");
   for(i=0;i<g.vexnum;i++)
   {
     for(j=0;j<g.vexnum;j++)
       printf("%11d",g.arcs[i][j]);
     printf("\n");
   }
   ShortestPath_FLOYD(g,p,d);
   printf("d矩陣:\n");
   for(i=0;i<g.vexnum;i++)
   {
     for(j=0;j<g.vexnum;j++)
       printf("%6d",d[i][j]);
     printf("\n");
   }
   for(i=0;i<g.vexnum;i++)
     for(j=0;j<g.vexnum;j++)
       printf("%s到%s的最短距離為%d\n",g.vexs[i],g.vexs[j],d[i][j]);
   printf("p矩陣:\n");
   l=strlen(g.vexs[0]); // 頂點向量字符串的長度
   for(i=0;i<g.vexnum;i++)
   {
     for(j=0;j<g.vexnum;j++)
     {
       if(i!=j)
       {
         m=0; // 占位空格
         for(k=0;k<g.vexnum;k++)
           if(p[i][j][k]==1)
             printf("%s",g.vexs[k]);
           else
             m++;
         for(n=0;n<m*l;n++) // 輸出占位空格
           printf(" ");
       }
       else
         for(k=0;k<g.vexnum*l;k++) // 輸出占位空格
           printf(" ");
       printf("   "); // 輸出矩陣元素之間的間距
     }
     printf("\n");
   }
 }