// algo7-6.cpp 實(shí)現(xiàn)算法7.15的程序。迪杰斯特拉算法的實(shí)現(xiàn)
 #include"c1.h"
 #define MAX_NAME 5 // 頂點(diǎn)字符串的最大長(zhǎng)度+1
 #define MAX_INFO 20 // 相關(guān)信息字符串的最大長(zhǎng)度+1
 typedef int VRType;
 typedef char InfoType;
 typedef char VertexType[MAX_NAME];
 #include"c7-1.h"
 typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 typedef int ShortPathTable[MAX_VERTEX_NUM];
 #include"bo7-1.cpp"

 void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
 { // 用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及帶權(quán)長(zhǎng)度
   // D[v]。若P[v][w]為T(mén)RUE,則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)。
   // final[v]為T(mén)RUE當(dāng)且僅當(dāng)v∈S,即已經(jīng)求得從v0到v的最短路徑 算法7.15
   int v,w,i,j,min;
   Status final[MAX_VERTEX_NUM];
   for(v=0;v<G.vexnum;++v)
   {
     final[v]=FALSE;
     D[v]=G.arcs[v0][v].adj;
     for(w=0;w<G.vexnum;++w)
       P[v][w]=FALSE; // 設(shè)空路徑
     if(D[v]<INFINITY)
     {
       P[v][v0]=TRUE;
       P[v][v]=TRUE;
     }
   }
   D[v0]=0;
   final[v0]=TRUE; // 初始化,v0頂點(diǎn)屬于S集
   for(i=1;i<G.vexnum;++i) // 其余G.vexnum-1個(gè)頂點(diǎn)
   { // 開(kāi)始主循環(huán),每次求得v0到某個(gè)v頂點(diǎn)的最短路徑,并加v到S集
     min=INFINITY; // 當(dāng)前所知離v0頂點(diǎn)的最近距離
     for(w=0;w<G.vexnum;++w)
       if(!final[w]) // w頂點(diǎn)在V-S中
         if(D[w]<min)
         {
           v=w;
           min=D[w];
         } // w頂點(diǎn)離v0頂點(diǎn)更近
     final[v]=TRUE; // 離v0頂點(diǎn)最近的v加入S集
     for(w=0;w<G.vexnum;++w) // 更新當(dāng)前最短路徑及距離
     {
       if(!final[w]&&min<INFINITY&&G.arcs[v][w].adj<INFINITY&&(min+G.arcs[v][w].adj<D[w]))
       { // 修改D[w]和P[w],w∈V-S
         D[w]=min+G.arcs[v][w].adj;
         for(j=0;j<G.vexnum;++j)
           P[w][j]=P[v][j];
         P[w][w]=TRUE;
       }
     }
   }
 }

 void main()
 {
   int i,j,v0=0; // v0為源點(diǎn)
   MGraph g;
   PathMatrix p;
   ShortPathTable d;
   CreateDN(g);
   ShortestPath_DIJ(g,v0,p,d);
   printf("最短路徑數(shù)組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到各頂點(diǎn)的最短路徑長(zhǎng)度為：\n",g.vexs[0]);
   for(i=1;i<g.vexnum;++i)
     printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);
 }