floyed.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include <iostream.h>
//多源最短路径的Floyed算法
#define MAX 10 //假定矩阵最大阶数为10,网中顶点数最多为10
#define BOUND 10000  // 程序中用10000代表∞,并将其命名为BOUND
int path[MAX][MAX];  // 记录从顶点i到顶点j的最短路径中间所经过的顶点
//递归函数,输出从结点i到结点j的最短路径中间所经过的结点
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是邻接矩阵
   //建立有向图,初始化相应数据   
	cout<<"输入顶点个数";   
	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]; //假定输入的权值是有效的正整数         
			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++) //两顶点间的路径经过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();
}