学步园

首先给出Floyd算法的实现代码

const int vexnum = 5;
const int maxval = 65536;/*图中表示不可达的长度*/
void Floyd(int G[][vexnum],int dist[][vexnum],int path[][vexnum])
{

	for(int i=0; i<vexnum; ++i)
		for(int j=0; j<vexnum; ++j)
		{
			/*initiate the dist[][] and path[][]*/
			dist[i][j] = G[i][j];
			if(i!=j && dist[i][j]<maxval)
			{	path[i][j] = i;}
			else
			{	path[i][j] = 0;}
		}
	

	for(int k=0; k<vexnum; ++k)
		for(int i=0; i<vexnum; ++i)
			for(int j=0; j<vexnum; ++j)
				if( dist[i][j] > dist[i][k]+dist[k][j] )
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = path[k][j];
				}
}

下面做一个简单测试（有向图如下）：

相应的邻接矩阵为：

  0,       50,     10,   maxval,    45,
maxval,     0,     15,   maxval,    10, 
maxval,   maxval,   0,     15,    maxval,
maxval,    20,    maxval,   0,      35,
maxval,   maxval, maxval,  30,       0

全部测试代码如下：

/*数组显示函数*/
void Display(int arr[vexnum][vexnum])
{
	for(int i=0;i<vexnum;++i)
	{
		for(int j=0;j<vexnum;++j)
			cout<<arr[i][j]<<'\t';
		cout<<endl;
	}
}

int main()
{
	/*准备数据 和 辅助记录数组*/
	int G[vexnum][vexnum] ={	
								   0,       50,     10,   maxval,    45,
								 maxval,     0,     15,   maxval,    10, 
								 maxval,   maxval,   0,     15,    maxval,
								 maxval,    20,    maxval,   0,      35,
								 maxval,   maxval, maxval,  30,       0
							};
	int dist[vexnum][vexnum]; /*记录最短距离*/
	int path[vexnum][vexnum]; /*记录最短路径*/

	/*执行算法*/
	Floyd(G,dist,path);

	/*显示邻接矩阵*/
	cout<<"graph:"<<endl;
	Display(G);

	/*显示最短距离*/
	cout<<"dist:"<<endl;
	Display(dist);
	
	/*显示最短路径*/
	cout<<"path:"<<endl;
	Display(path);
	
	system("pause");

	return 0;
}

测试结果为：

dist  中 65536表示无法到达

path 中对角线上的0表示自身，非对象线的元素表示，要到达这个节点需要到达的上一个结点，如 v0->v3，path值为2，需要先到达v2, v0->v2 path值为0，即从v0开始即可，所以v0到v3的最短路径是v0->v2->v3.