day 62 | Floyd
没想到还有一天，
然后描述一下 floyd 的算法,
核心就是遍历点作为中间的节点来获取最短的路径。
节点i 到 节点j 的最短路径允许经过节点 k 的最短路径分两种情况：
- 节点i 到 节点j 的最短路径经过节点k
- 节点i 到 节点j 的最短路径不经过节点k
dp[i][j][k] = min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1])
我们把 节点 0 的情况设置为初始值
遍历顺序就是每次选一个节点作为中间节点，然后遍历所有节点。先 k 再 ij
查看1道真题和解析
腾讯成长空间 6021人发布
