代码随想录算法训练营第六十一天 | floyd算法
Floyd 算法精讲
题目链接：97. 小明逛公园
文章讲解：代码随想录
思想：本题是多源最短路，即求多个起点到多个终点的多条最短路径。用Floyd 算法。
Floyd 算法对边的权值正负没有要求，都可以处理，Floyd算法核心思想是动态规划。
动规五部曲：
1、确定dp数组（dp table）以及下标的含义
grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。
2、确定递推公式
（1）节点i 到 节点j 的最短路径经过节点k
对于第一种情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点k 的最短距离是不经过节点k，中间节点集合为[1...k-1]，所以表示为grid[i][k][k - 1]
节点k 到节点j 的最短距离也是不经过节点k，中间节点集合为[1...k-1]，所以表示为 grid[k][j][k - 1]
（2）节点i 到 节点j 的最短路径不经过节点k
第二种情况，grid[i][j][k] = grid[i][j][k - 1]
如果节点i 到 节点j的最短距离不经过节点k，那么中间节点集合[1...k-1]，表示为 grid[i][j][k - 1]
因为我们是求最短路，对于这两种情况自然是取最小值。
即： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])
3、dp数组如何初始化
把k 赋值为 0，本题节点0是无意义的，节点是从1 到 n，在下一轮计算的时候，就可以根据 grid[i][j][0] 来计算 grid[i][j][1]，此时的 grid[i][j][1] 就是 节点i 经过节点1 到达 节点j 的最小距离了。
本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数
4、确定遍历顺序
好比是一个三维坐标，i和j是平层，而k 是垂直向上的。遍历的顺序是从底向上一层一层去遍历。
所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。
5、举例推导dp数组
