floyd算法path数组和dist数组（递归打印路径）

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;

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

如果稍微改一下path数组
path[1][3]=4;
path[1][4]=-1;
path[4][3]=-1;
则0到2节点的最短路径为:
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