Floyd 算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与 Dijkstra 算法类似。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特 · 弗洛伊德命名。
状态转移方程： f[i,j]=min{f[i,k]+f[k,j],f[i,j]}，注意：点k作为最外层循环。时间复杂度为 O(n3)，
算法描述：
1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w （一般称为中间点）使得从 u 到 w 再到 v 比已知的路径更短。如果是，松弛它。
3. 遍历直到结束，这时候存储图的数据结构就得到了多源最短路径。
传递闭包 概念：给定一个集合，以及若干元素的传递关系，传递闭包问题是求解所有元素的联通关系，如给定集合 {a,b,c} ，已知 a->b，b->c，我们可以推出 a->c 。
如果是借已知单向图推两点间的联通关系，可以用 DFS 或 BFS, 复杂度为 O(n+m)。但是求解传递闭包问题时，我们需要求得所有点对之间的联通关系，复杂度就达到了 O(n*(n+m)) ，在稠密图中，复杂度约等于O(n3) ，这么高的复杂度，我们可以用相同复杂度但是代码简单的Floyd进行处理。
具体方案是用点对间的联通关系来代替原本的路径长度进行递推。
若 dp[i][k]=1 并且 dp[k][j]=1（等于 1 表示两节点联通），则说明节点i可以借由节点k到达节点j。
动态转移方程就变成了：dp[i][j] |= dp[i][k] & dp[k][j]
传递闭包的Floyd代码：
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dp[i][j] |= dp[i][k] & dp[k][j];简单优化一下：先判断 dp[i][k] 是否为 1 再进入 j 的循环，可以减少一点计算时间。
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
if(dp[i][k])
for(int j = 1; j <= n; ++j)
if(dp[k][j])
dp[i][j] = 1;复杂度还是 O(n3) 。但实际上这个代码还能再进行优化，因为 dp 数组中的值只有 0 和 1 。而且最后一层里，dp[k][j] 为 1 时将 dp[i][j] 赋值为 1 ，这个操作其实可以用或操作来取代。所以终极的优化就是使用 bitset ，既可以存 0、1，还可以直接进行位运算。 具体代码如下：
bitset<N> dp[N];
void Floyd(){
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
if(dp[i][k])
dp[i] |= dp[k];
}最后复杂度降为了 O(n2) ，优于直接搜索，可以处理 1000 的数据量。