// algo7-11.cpp 實現教科書圖7.33的程序(新增孤立頂點臺北)
 #include"c1.h"
 #include"func7-1.cpp" // 包括頂點信息類型的定義及對它的操作
 #include"func7-2.cpp" // 包括弧(邊)的相關信息類型的定義及對它的操作
 #include"c7-1.h" // 圖的數組(鄰接矩陣)存儲結構
 #include"bo7-1.cpp" // 圖的數組(鄰接矩陣)存儲結構的基本操作
 typedef char PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 // 三維數組，其值只可能是0或1，故用char類型以減少存儲空間的浪費
 typedef VRType DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二維數組
#include"func7-8.cpp" // 求有向網中各對頂點之間最短距離的Floyd算法

 void path(MGraph G,PathMatrix P,int i,int j)
 { // 求由序號為i的起點城市到序號為j的終點城市最短路徑沿途所經過的城市
   int k,m=i; // 起點城市序號賦給m
   printf("依次經過的城市：\n");
   while(m!=j) // 未到終點城市
   { G.arcs[m][m].adj=INFINITY; // 對角元素賦值無窮大
     for(k=0;k<G.vexnum;k++)
       if(G.arcs[m][k].adj<INFINITY&&P[m][j][k])
       { // m到k有直接通路，且k在m到j的最短路徑上
         printf("%s ",G.vexs[m].name);
         G.arcs[m][k].adj=G.arcs[k][m].adj=INFINITY; // 將直接通路設為不通
         m=k; // 經過的城市序號賦給m，繼續查找
         break;
       }
   }
   printf("%s\n",G.vexs[j].name); // 輸出終點城市
 }

 void main()
 {
   MGraph g;
   int i,j,k,q=1;
   PathMatrix p; // 三維數組
   DistancMatrix d; // 二維數組
   char filename[8]="map.txt"; // 數據文件名
   CreateFromFile(g,filename,0); // 通過文件map.txt構造沒有相關信息的無向網g
   for(i=0;i<g.vexnum;i++)
     g.arcs[i][i].adj=0;
     // ShortestPath_FLOYD()要求對角元素值為0，因為兩點相同，其距離為0
   ShortestPath_FLOYD(g,p,d); // 求每對頂點間的最短路徑，在func7-8.cpp中
   while(q)
   { printf("請選擇：1 查詢  0 結束\n");
     scanf("%d",&q);
     if(q)
     { printf("城市代碼：\n");
       for(i=0;i<g.vexnum;i++)
       { printf("%2d.%-8s",i+1,g.vexs[i].name);
         if(i%7==6) // 輸出7個數據就換行
           printf("\n");
       }
       printf("\n請輸入要查詢的起點城市代碼 終點城市代碼：");
       scanf("%d%d",&i,&j);
       if(d[i-1][j-1]<INFINITY) // 有通路
       { printf("%s到%s的最短距離為%d\n",g.vexs[i-1].name,g.vexs[j-1].name,
         d[i-1][j-1]);
         path(g,p,i-1,j-1); // 求最短路徑上由起點城市到終點城市沿途所經過的城市
       }
       else
         printf("%s到%s沒有路徑可通\n",g.vexs[i-1].name,g.vexs[j-1].name);
       printf("與%s到%s有關的p矩陣：\n",g.vexs[i-1].name,g.vexs[j-1].name);
       for(k=0;k<g.vexnum;k++)
         printf("%2d",p[i-1][j-1][k]);
       printf("\n");
     }
   }
 }