多源最短路：Floyd算法の暴力美学

多源最短路求解的是图中的任意两个节点之间的最短路。
前文我们已经讲过单源最短路，我们完全可以做n次单源最短路算法，求出任意两节点的最短隔断。最快的堆优化版的 dijkstra 算法的时间复杂度为o（m * logm），摆列n次时间复杂度变为o（n * m * logm）。
但是我们下文介绍的基于动态规划实现的Floyd算法中阶段性求解的方法才是多源最短路中最重要的。
Floyd算法

Floyd算法的本质是动态规划，也叫做插点法。通过不断在两点之间插入新的结点来更新最短路。
留意：Floyd算法适用于任何可以求解最短路的图，也就是说不能有负环。

1. 状态表示：f[k][j] ：表示仅仅颠末【1 - k】这些结点时，i 到 j的最短路。
2. 状态转移方程：分析方法和背包题目相似。

1. f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j])  

复制代码

3. 空间优化：由于是一层一层的遍历，以是我们可以去除第一维。
4. 填表顺序：填表的时间依赖的是 k - 1层的状态，以是肯定要从 k 开始摆列。然后填表的时间正常从左到右，从上到下填。
5. 初始化：由于我们要做min操纵，以是开始时要把所有的状态初始化成INF，从i 到 i 的最短路是零，所有还要把 f 初始化成零（i从1 到 n）。
6. 终极结果：任意两个i j 就是两点间的最短路了。

---

B3647 【模板】Floyd - 洛谷

题目来源：洛谷
题目难度：★

【解题】：一道模板题啦~