Floyd求最短路径 其中有两个数组,一个是dist[][],一个是path[][]
dist[][]
dist[i][j]表示i到j的最短路径长度,这个很好理解
paht[][]
【acm笔记|floyd算法path数组和dist数组(递归打印路径)】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<";
else{
printPath(i,path[i][j]);
printPath(path[i][j],j);
}
cout<
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点(详细介绍 Python 中的 7 种交叉验证方法!)
- 网络|简单聊聊压缩网络