定义 $d_{ij}^{(k)}$ 为只考虑 $i$ 到 $j$ 的路径中只包含前 $k$ 个点的时候，从 $i$ 到 $j$ 的最短路径。
动态规划的思想，我们考虑 $d_{ij}^{(k)}$ 和 $d_{ij}^{(k-1)}$ 的关系，当加入点 $k$ 的时候，也许通过点 $k$，可以更新从 $i$ 到 $j$ 的最短路径。
即 $d_{ij}^{(k)} = min(d_{ij}^{(k)}, d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$

初始条件$\begin{equation}d_{ij}^{0}=\begin{cases} 0 & ,i==j \\\ w(i,j) & ,i\text{到}j\text{有边} \\\ INF & , i\text{到}j\text{没有边}\end{cases}\end{equation}$

代码实现：

// 如果你决定用floyd的话，那么存图就可以用邻接矩阵（因为已经没有省时间的必要了qwq） 
// 邻接矩阵：用来存两点之间的边 
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (i == j) d[i][j] = 0; // d数组表示两点之间的最短路径 
        else if (w[i][j]) d[i][j] = w[i][j]; // w数组表示两点之间的权值 
        else d[i][j] = INF;
    }
}
for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
} 

注意 $INF$ 的选择，不要太大，避免 $INF + INF$ 溢出

如果在一个图论题中，如果点的个数不超过 $500$，那么可以考虑用 $floyd$
通常情况下是用 $floyd$ 做一个预处理，然后套别的算法来解决问题

Floyd计算传递闭包

在有向图中，$d[i][j]$ 如果是 $1$，表示 $i$ 能到达 $j$。否则是 $0$ 表示无法到达。根据初始到达关系，计算最终一个点能到达的其他点。

代码实现：

for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
        }
    }
} 

一些练习题

1. New Year Permutation
2. 产生数
3. [USACO4.1]篱笆回路Fence Loops
4. 灾后重建
5. Secret Chamber at Mount Rushmore
6. String Problem
7. [JSOI2007]重要的城市
8. Roads in Berland
9. Greg and Graph
10. Travel by Car
11. [USACO07NOV]Cow Hurdles S
12. 医院设置
13. 山上的国度
14. 除法求值
15. Shortest Path Queries 2