// algo7-6.cpp 實現算法7.15的程序。迪杰斯特拉算法的實現
 #include"c1.h"
 #define MAX_NAME 5 // 頂點字符串的最大長度+1
 #define MAX_INFO 20 // 相關信息字符串的最大長度+1
 typedef int VRType;
 typedef char InfoType;
 typedef char VertexType[MAX_NAME];
 #include"c7-1.h" // 鄰接矩陣存儲表示
 #include"bo7-1.cpp" // 鄰接矩陣存儲表示的基本操作
 typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 路徑矩陣，二維數組
 typedef int ShortPathTable[MAX_VERTEX_NUM]; // 最短距離表，一維數組

 void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)
 { // 用Dijkstra算法求有向網G的v0頂點到其余頂點v的最短路徑P[v]及帶權長度
   // D[v]。若P[v][w]為TRUE，則w是從v0到v當前求得最短路徑上的頂點。
   // final[v]為TRUE當且僅當v∈S，即已經求得從v0到v的最短路徑 算法7.15
   int v,w,i,j,min;
   Status final[MAX_VERTEX_NUM]; // 輔助矩陣，為真表示該頂點到v0的最短距離已求出，初值為假
   for(v=0;v<G.vexnum;++v)
   {
     final[v]=FALSE; // 設初值
     D[v]=G.arcs[v0][v].adj; // D[]存放v0到v的最短距離，初值為v0到v的直接距離
     for(w=0;w<G.vexnum;++w)
       P[v][w]=FALSE; // 設P[][]初值為FALSE，沒有路徑
     if(D[v]<INFINITY) // v0到v有直接路徑
       P[v][v0]=P[v][v]=TRUE; // 一維數組p[v][]表示源點v0到v最短路徑通過的頂點
   }
   D[v0]=0; // v0到v0距離為0
   final[v0]=TRUE; // v0頂點并入S集
   for(i=1;i<G.vexnum;++i) // 其余G.vexnum-1個頂點
   { // 開始主循環，每次求得v0到某個頂點v的最短路徑，并將v并入S集
     min=INFINITY; // 當前所知離v0頂點的最近距離，設初值為∞
     for(w=0;w<G.vexnum;++w) // 對所有頂點檢查
       if(!final[w]&&D[w]<min) //在S集之外的頂點中找離v0最近的頂點，并將其賦給v，距離賦給min
       {
	 v=w;
	 min=D[w];
       }
     final[v]=TRUE; // 將v并入S集
     for(w=0;w<G.vexnum;++w) // 根據新并入的頂點，更新不在S集的頂點到v0的距離和路徑數組
       if(!final[w]&&min<INFINITY&&G.arcs[v][w].adj<INFINITY&&(min+G.arcs[v][w].adj<D[w]))
       { // w不屬于S集且v0→v→w的距離＜目前v0→w的距離
         D[w]=min+G.arcs[v][w].adj; // 更新D[w]
	 for(j=0;j<G.vexnum;++j) // 修改P[w]，v0到w經過的頂點包括v0到v經過的頂點再加上頂點w
	   P[w][j]=P[v][j];
	 P[w][w]=TRUE;
       }
   }
 }

 void main()
 {
   int i,j;
   MGraph g;
   PathMatrix p; // 二維數組，路徑矩陣
   ShortPathTable d; // 一維數組，最短距離表
   CreateDN(g); // 構造有向網g
   Display(g); // 輸出有向網g
   ShortestPath_DIJ(g,0,p,d);//以g中位置為0的頂點為源點，球其到其余各頂點的最短距離。存于d中
   printf("最短路徑數組p[i][j]如下:\n");
   for(i=0;i<g.vexnum;++i)
   {
     for(j=0;j<g.vexnum;++j)
       printf("%2d",p[i][j]);
     printf("\n");
   }
   printf("%s到各頂點的最短路徑長度為：\n",g.vexs[0]);
   for(i=0;i<g.vexnum;++i)
     if(i!=0)
       printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);
 }