#include <iostream.h>
//多源最短路徑的Floyed算法
#define MAX 10 //假定矩陣最大階數(shù)為10,網(wǎng)中頂點數(shù)最多為10
#define BOUND 10000  // 程序中用10000代表∞,并將其命名為BOUND
int path[MAX][MAX];  // 記錄從頂點i到頂點j的最短路徑中間所經(jīng)過的頂點
//遞歸函數(shù),輸出從結點i到結點j的最短路徑中間所經(jīng)過的結點
void outPath(int i,int j)
{  int k=path[i][j];   
	if(k>=0)    
	{  outPath(i,k);       
		cout<<","<<k;       
		outPath(k,j);   
	}
}
//最短路徑Floyed算法
void shortPathFloyd()
{  int temp[MAX][MAX],cost[MAX][MAX]; //temp是運算過程矩陣A,cost是鄰接矩陣
   //建立有向圖,初始化相應數(shù)據(jù)   
	cout<<"輸入頂點個數(shù)";   
	int count;   
	cin>>count; //假定其不會超過MAX   
	cout<<"依次輸入各弧權值(-1代表兩頂點之間無弧)";   
	int row, col;   
	for(row=0; row<count; row++) 
		for(col=0; col<count; col++)       
		{  cin>>cost[row][col]; //假定輸入的權值是有效的正整數(shù)         
			if(cost[row][col]==-1) cost[row][col]=BOUND;          
			temp[row][col]=cost[row][col]; //temp矩陣初始化         
			path[row][col]=-1;      
		}   
	for(int k=0; k<count; k++)      
		for(row=0; row<count; row++)         
			for(col=0; col<count; col++) //兩頂點間的路徑經(jīng)過k是否還可縮短長度            
				if(temp[row][k]+temp[k][col] <temp[row][col])            
				{  temp[row][col]=temp[row][k]+temp[k][col];               
					path[row][col]=k;             
				}    
	for(row=0; row<count; row++) // 輸出兩頂點間的最短路徑及長度      
		for(col=0; col<count; col++)         
			if(row!=col) 
				if(temp[row][col]==BOUND)   
					cout<<"from "<<row<<" to "<<col<<"NoPath !\n";
				else          
				{  cout<<"("<<row; outPath(row,col);               
					cout<<","<<col<<")   length="<<temp[row][col]<<endl;            
				}  
}

void main() {
	shortPathFloyd();
}