多源最短路：Floyd算法の暴力美学
多源最短路求解的是图中的任意两个节点之间的最短路。前文我们已经讲过单源最短路，我们完全可以做n次单源最短路算法，求出任意两节点的最短隔断。最快的堆优化版的 dijkstra 算法的时间复杂度为o（m * logm），摆列n次时间复杂度变为o（n * m * logm）。
但是我们下文介绍的基于动态规划实现的Floyd算法中阶段性求解的方法才是多源最短路中最重要的。
Floyd算法
Floyd算法的本质是动态规划，也叫做插点法。通过不断在两点之间插入新的结点来更新最短路。
留意：Floyd算法适用于任何可以求解最短路的图，也就是说不能有负环。
1. 状态表示：f ：表示仅仅颠末【1 - k】这些结点时，i 到 j的最短路。
2. 状态转移方程：分析方法和背包题目相似。
https://i-blog.csdnimg.cn/direct/f6ee6181a62b4edc925f75fcd34a3ee1.png
f = min(f, f + f) 3. 空间优化：由于是一层一层的遍历，以是我们可以去除第一维。
4. 填表顺序：填表的时间依赖的是 k - 1层的状态，以是肯定要从 k 开始摆列。然后填表的时间正常从左到右，从上到下填。
5. 初始化：由于我们要做min操纵，以是开始时要把所有的状态初始化成INF，从i 到 i 的最短路是零，所有还要把 f 初始化成零（i从1 到 n）。
6. 终极结果：任意两个i j 就是两点间的最短路了。
B3647 【模板】Floyd - 洛谷
题目来源：洛谷
题目难度：★
https://i-blog.csdnimg.cn/direct/baff3f6ad4444b7ea614bc963b2de294.png
【解题】：一道模板题啦~
https://i-blog.csdnimg.cn/direct/66301c02a550410598c08a813a70693b.jpeg
页:
[1]