Floyd

为数不多的全源最短路算法，全源即，全部点为原点，即算出任意两个点之间的最短路径。
前提条件，没有负环。可有负权。
因为中心思想是动态规划，所以有很强的性质，做题的时候注意利用。

中心思想

中心思想为动态规划。
现在我们设 f[k][i][j] 表示从点 \(i\) 到点 \(j\)，只经过 \(1\) 到 \(k\) 的最短距离。

初始化，当 \(k=0\) 时 f[0][i][j] 的值仅为 \(i\) 到 \(j\) 的边权，\(0\) 或者 \(+\infty\)。当 \(i = j\) 时为 \(0\)，即到自身的距离为 \(0\)；当 \(i\not=j\) 时，\(i\) 和 \(j\) 之间有权值则为权值，无权值则为 \(+\infty\)。
当 \(k\ge1\) 时，有 f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]) 即经过点 \(k\) 看是否能松弛 \(i\) 和 \(j\) 之间的距离。

时间复杂度也显而易见 \(O(n^3)\)

注意本质。

正确性

本质是动态规划，正确性显而易见，当 \(k=n\) 时，即可以经历所有点去松弛，自然可以得到最短路径，但是如果有负环，因为算法不能无限进行负环操作，因此，不能得出负无穷。

实际操作

1. 初始化之后，从 \(1\) 到 \(n\) 枚举 \(k\) 的大小
2. 枚举 \(i\) 点
3. 枚举 \(j\) 点
4. 根据转移方程，进行转移
5. 重复上述操作

代码

很简单就三个 for

for (int i = 1; i <= n; i ++ )
	for (int j = 1; j <= n; j ++ )
		f[0][i][j] = g[i][j];

for (int k = 1; k <= n; k ++ )
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			f[k][i][j] = max(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]);

因为是动态规划，转移又只涉及上一维，所以可以优化一维空间。
最常用的也是这种。

for (int k = 1; k <= n; k ++ )
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			f[i][j] = max(f[i][j], f[i][k] + f[k][j]);