欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

floyd算法path数组和dist数组(递归打印路径)

程序员文章站 2022-03-13 17:18:05
Floyd求最短路径其中有两个数组,一个是dist[][],一个是path[][]dist[][]dist[i][j]表示i到j的最短路径长度,这个很好理解paht[][]path[i][j]表示,i到j节点的路径中,j节点的直接前驱例如:path数组中path[0][2]=3;path[0][3]=1;path[0][1]=0;path[0][0]=-1;//-1表示没有直接前驱,也就是没有通过中间节点通过上面的数组可以得到0到2节点的最短路径为0-->1-->...

Floyd求最短路径

其中有两个数组,一个是dist[][],一个是path[][]


dist[][]

dist[i][j]表示i到j的最短路径长度,这个很好理解

paht[][]

path[i][j]表示,i到j节点的路径中,j节点的直接前驱
例如:

path数组中
path[0][2]=3;// 2的直接前驱为3
path[0][3]=1;// 3的直接前驱为1
path[0][1]=-1;//-1表示没有直接前驱,也就是没有通过中间节点
path[1][3]=-1;
paht[3][2]=-1;

通过上面的数组可以得到
02节点的最短路径为:
0-->1-->3-->2
---------------------------------------------------------------

如果稍微改一下path数组
path[1][3]=4;
path[1][4]=-1;
path[4][3]=-1;02节点的最短路径为:
0-->1-->4-->3-->2

代码实现可以利用递归,实现也不难:
//伪代码,没有测试,有错希望指正
void printPath(int i,int j){
	if(path[i][j]==-1)
		cout<<i<<"-->";
	else{
		printPath(i,path[i][j]);
		printPath(path[i][j],j);
		}
	cout<<j;
		
}

本文地址:https://blog.csdn.net/qq_40733911/article/details/107393072