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;
通过上面的数组可以得到
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