图论中一个重要的问题是最短路径问题。
这个问题是在离散数学课上报考，在数据结构和算法课上报考，在图论课上报考，在计算机网络上报考.
解决最短路径问题有几种有名的算法：
1.dijkstra算法，最经典的单源最短路径算法
2.bellman-ford算法、允许负权重边缘的单源最短路径算法
3.spfa其实是bellman-ford队列的优化，其实和bfs的关系更密切
4.floyd算法，经典多源最短路径算法
今天讨论floyd算法。 它用于解决多源最短路径问题，算法的时间复杂度为o(n3 )。
floyd算法为什么经典，是因为只有五行(或四行)！
是的，我没特意写一行代码。
因为这个算法非常短，所以我们通常记住它并将其用作模板，而不是像学习dijkstra时那样一步一步地了解它是如何贪婪的。
那为什么floyd算法是这样的呢？ 或者，为什么这样就能求出从所有点到所有点的最短路径？
谈floyd算法，一般说这是动态规划算法。 ((怪不得这么美) )。
为什么是动态规划算法？ 那是因为有递归公式：d[I][j]=min(d[I][j]，d[i][k] d[k][j] )。
另一个是三重环路。 k写外面。 其中的I，j是对称的。 没有什么可以随便嵌套的。
这可能就是我们大多数人对floyd算法的了解。
那么，我们其实没有解决核心问题。 为什么这样能解决问题，为什么是这个递归公式，是这个嵌套顺序吗？
这没有前辈说的那么明显.
事实上，一旦了解了贝尔曼福德的正确性，就知道为什么floyd是可能的。
这里不讨论floyd以外的算法。 我刚从正面做了流体。
floyd最重要的地方是其递归公式，抽象地写着该递归公式的是下图：
简而言之，这个从I到j的最短路径是子问题，从I到k的最短路径和从k到j的最短路径。
即，可以列举中间点k，找到最小的d[i][k] d[k][j]，并且将其设定为d[i][j]的最小值。
这似乎很合理啊。 假设所有d[i][k]和d[k][j]都取最小值，则此dp为dp。
但是，d[i][k]和d[k][j]也不一定一开始就取了最小值。 和d[i][j]一样，会越来越小。
那么，不会吧？ d[i][j]取最小值时的k是某个x。
另一方面，在最外循环k=x的情况下，d[i][x]或d[x][j]没有取最小值，但在这种情况下，d[I][j]=min(d[I][j]，d [ I ] [ x ] d [ x ]
答案当然不会发生这种事。 我们今天的重点是讨论为什么不会发生这种事。
需要证明致命的结论：
假设I和j之间最短路径上的节点集合(不含I，j )，编号最大的是x，则当外循环k=x时，d[i][j]一定得到最小值。
怎样证明，才能使用强归纳法？
假设I到x的中间号最大的是x1，x到j的中间号最大的是x2。
x从I到j的中间号最大，所以明显是x1x、x2x。
结论表明，当k=x1时d[i][x]已经取得最小值，当k=x2时d[x][j]已经取得最小值。
那么当k=x时，d[i][x]和d[x][j]一定取最小值。
因此，如果k=x，则运行d[i][j]=min(d[I][j]，d[i][x] d[x][j] )时，一定会得到d[I][j]的最小值。
证完。
用强归纳法证明是美丽但抽象的，忽视了初始情况和特殊情况(如I和j之间没有节点)。
那么，举个实际的例子来说明其正确性吧。
上图是从1到5的最短路径，这意味着d[1][2]、d[2][4]、d[4][3]、d[3][5]从一开始就是最小值。
这在一定程度上证明了我们的那个结论。 因为中间没有节点，所以最大号码是-，k=-。 也就是说，从一开始就取最小值。
首先，可以看出，第一回合k=1原本在1点到5点之间无法取得最短距离，但更新后也无法保证取得最短距离。
在第二次k=2时，发现d[1][4]一定取最小值。 这是因为： d[1][4]=min(d[1][4]，d[1][2] d[2][4]被执行，d[1][2]和d[4]
发现在第三次k=3时，d[4][5]一定取了最小值。
第四轮k=4最关键,我们发现d[2][3],d[1][3],d[2][5],d[1][5]都肯定取得了最小值.d[2][3]=d[2][4]+d[4][3]
d[1][3]=d[1][4]+d[4][3]
d[2][5]=d[2][4]+d[4][5]
d[1][5]=d[1][4]+d[4][5]
我们可以看到,等号右边的几个值,都在k=4之前取得了最小值.
这意味着d[1][3]的更新就是最小的了,不会存在d[1][4]未取最小值导致d[1][3]未取得最小的情况发生.
并且,我们看到1到4之间的最大编号是2,而d[1][4]在k=2时肯定取得了最小值,后面的也是同理.
这在感性上证明了我们那个致命的结论.
有了这个致命的结论,根据一开始的推理,其实已经可以显然地理解为什么floyd是正确的了.
事实上,假如在执行d[i][j]=min(d[i][j],d[i][k]+d[k][j])前,对于所有的k,d[i][k]和d[k][j]都是最小值,那么上面例子里d[1][5]之间的k可以选择2,3,4.
但是,我们没法做到对于所有的k,执行那个语句前d[i][k]和d[k][j]都是最小值.
但是,我们保证了能存在一个k=x,在执行那个语句前d[i][x]和d[x][j]都是最小值.
而这个x,是i和j最短路径的点集里最大的编号.
这也说明了为什么k一定要是在最外层的原因,
因为假如k在最里层,那么d[i][j]=min(d[i][j],d[i][k]+d[k][j])是一次性执行完.
那么我们就要保证,在这时候,至少存在一个k=x,使得d[i][x]和d[x][j]都是取得了最小值.
然而在这种情况下我们并不能保证,但如果k在最外层就可以保证了.