//最短路徑SShortP1.cpp
//所有頂點之間的最短路徑
#include<iostream.h>
#include<iomanip.h>
#include "graph.cpp"
#include "PShortP.h"
template<class T>
void Make2DArray(int **&a,int row,int col)
//定義二維動態數組a,其行數為row,列數為col
{a=new T*[row];//a為指針數組,長度為row
 for(int i=0;i<row;i++)
  a[i]=new T[col];//每個指針指向一個一維數組,長度為col
}
void SShortPath(AdjMatrix &G,int **dist,int **path)
{int n=G.NumV();
 for(int i=0;i<n;i++)
  PShortPath(G,i,dist[i],path[i]);
}
//算法測試
void main()
{cout<<"SShortP1.cpp運行結果:\n";
 int n=6,k1=1,k2=1,i,j;
 AdjMatrix g(n,k2);
 g.CreateMatrix(n,k1,k2);
 cout<<"輸出鄰接矩陣相應圖的頂點:\n";
 g.Creatgraph(n,k2);
 
 int m=g.NumV();
 int **dist,**path;
 Make2DArray<int>(dist,m,m);
 Make2DArray<int>(path,m,m);
 SShortPath(g,dist,path);
 for(i=0;i<m;i++)
 {cout<<"從頂點"<<g.GetValue(i)
      <<"到其他各頂點的最短距離為:\n";
  for(j=0;j<m;j++)
   cout<<"到頂點"<<g.GetValue(j)
       <<"的最短距離為:"<<dist[i][j]<<endl;
   cout<<"從頂點"<<g.GetValue(i)
       <<"到其他各頂點的最短路徑的前一頂點為:\n";
   for(j=0;j<m;j++)
    if(path[i][j]!=-1)
     cout<<"到頂點"<<g.GetValue(j)<<"的前一頂點為:"
         <<g.GetValue(path[i][j])<<endl;
 }
 cin.get();cin.get();}