#include "p284b.cpp"
void Graph::AllLengths ( )
{
//Edge[n][n]是一個具有n個頂點的圖的鄰接矩陣。a[i][j]是頂點i和j之間的最短路徑長度。path[i][j]是相應路
//徑上頂點j的前一頂點的頂點號, 在求最短路徑時圖的類定義中要修改path為path[NumVertices][NumVertices]。
   for ( int i=0; i<n; i++ )
      for ( int j=0; j<n; j++ ) {							//矩陣a與path初始化
	 if (i!=j) dist[i][j] = Edge[i][j]; else dist[i][j]=0;
	 if ( i != j && dist[i][j] < MAXINT ) path[i][j] = i;			//有路徑
	 else path[i][j] =-1;							// i到j無路徑
      }
   for ( int k=0; k<n; k++ )							//產生a(k)及相應的path(k)
	 for ( i=0; i<n; i++ )
	   if (path[i][k]>=0)
	   for ( int j=0; j<n; j++ )
		 if
		 (
		  path[k][j]>=0 &&
		  dist[i][k] + dist[k][j] < dist[i][j] )
		 {
		   dist[i][j] = dist[i][k] + dist[k][j];
		   path[i][j] = path[k][j];		//縮短路徑長度, 繞過k到j
		 }
}