多源是指它可以求出以每个点为起点到其他每个点的最短路
不过其实有一种情况求不出最短路，就是有负环的情况，此时可以不断地在环中转圈，而Floyd算法无法判断这样的情况，所以就只能在没有负环的情况下使用。

概述

Floyd算法是一种利用动态规划的思想，计算给定的带权图中任意两个顶点之间的最短路径的算法，无权图可以把每个边的边权看作1.
我们用$dp[k][i][j]$表示$i$到$j$能经过$1$~$k$的点的最短路，那么实际上$dp[0][i][j]$就是原图，如果$i,j$之间存在边，那么$i,j$之间不经过任何点的最短路就是边长，否则，$i,j$之间的最短路是无穷大
那么对于$i,j$之间经过$1$ ~ $k$的最短路$dp[k][i][j]$可以通过经过$1$ ~ $k-1$的最短类路转移过来

• 如果不经过第k个点，那么就是$dp[k-1][i][j]$
• 如果经过第k个点，那么就是$dp[k-1][i][k]+dp[k-1][k][j]$

所以就有了动态转移方程
$$dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]$
也就可以写出代码：

int g[N][N];  // 邻接矩阵存图
int dp[N][N][N];
void floyd(int n) {
    for (int k = 0; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (k == 0) { // 初始化
                    dp[k][i][j] = g[i][j];
                } else { // 状态转移
                    dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们仔细分析可以发现，$dp[k]$可以由$dp[k-1]$转移过来。并且$dp[k-1][i][k]=dp[k][i][k]$，因为$i$到$k$的最短路中间肯定不会经过k。同理$dp[k-1][k][j]=dp[k][k][j]$
那么动态转移方程实际上就变成了
$$dp[k][i][j]=min(dp[k-1][i][j],dp[k][i][k]+dp[k][k][j]$$
这时候，我们尝试把k这一维度去掉，就用$dp[i][j]$来表示$i,j$之间的最短路，那么专一就变成了
$$\forall 1\le k\le ndp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])$
这时候，dp数组已经退化到g数组了
综上所述，我们就可以写出最终的Floyd算法，也是最常用的写法，优化了一维空间。并且写法更加简单。如果您理解了动态规划的思想，那么您一定很容易就能明白枚举中间点$k$为什么一定要写在最外面。如果没有理解这一点，很容易把3个循环的顺序弄错。
刚才分析得出，最后的dp数组退化成了g数组，所以可以直接在原数组上操作
参考代码：

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 101;
int g[N][N];
void Floyd(int n) {
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
int main() {
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < N; i++) {
        g[i][i] = 0;
    }
    int n, m;
    int u, v, w;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    Floyd(n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36