算法介绍

Floyd参考：这位作者的代码和公式已经非常棒了，所以对于过程和定义就不过多赘述了

排序法证明

其实上文链接也有证明过程，也有去翻过其他博客，基本都是这个证明过程，不过这个证明过程有些问题。
该证明过程的前提条件是点集内部是从小到大排序的，证明原理就是当求到k时，小于k的都已经得到最优解。
这样的证明限制了点集序号必须严格排序计算，但实际在计算过程中，点序是任意的，倒序、随机抽取都可，所以排序法的证明相对局限。

倒序： 6 5 4 3 2 1
奇偶互换：2 1 4 3 6 5
随机抽取：2 5 1 3 4 6

这里就不贴代码了，总之试过都AC了。

图解证明

由于各点之间没有顺序关系，为了避免误会，这里就不用1234…来标记了，直接用等价字母替代。
我们最终的目的是找一条最短路径，通往a->k，假设存在这么一条最短路径，即下图：
在这里插入图片描述
从a开始，经过许多点，最终到达k，此路径是最短的，故这里相邻两点之间肯定是互相连通着的。
或许会有e->m->g但由于不是最优路径，所以就被省略了，能够显示在这里的，说明就是最优的路线，下文会讲述如何将最优的路线串联起来。

1. 最优解集合的初始化

首先我们任意取一点：e
我们不考虑其他点，只考虑e本身和其临近点，即：{d,e,f}
在这里插入图片描述
可以发现能够得到 {d,e,f} 中任意两点间的最优解，即这个点集中互相到达情况下的最短路径。
由于我们看到的就是答案（最短路径）：dis[d][f]=dis[d][e]+dis[e][f] dis[d][e]=dis[d][e] dis[e][f]=dis[e][f]
这里主要就是想说明，我们已经得到了关于这三个点相互到达的最优解的集合{d,e,f}。

2. 最优解集合的扩大

在这里插入图片描述
我们紧接着再假设下一个选取的点为：f
我们可以发现在 {d、e、f}点集中，以f为跳板，可以与g取得联系；
例如dis[d][g]=dis[d][f]+dis[f][g]，从d->g的路线即d->e->f->g。

Floyd算法会将任意两点间以f为跳板，计算出其中最短的路径，最终在这个{d,e,f,g}点集中，任意两点都是最短路径。
所以我们的最优解集合最终成为：
在这里插入图片描述

3. 最优解集合的合并

由于是随机选择，出现下面情况的可能性也是非常大的。
我们依次选择了e,f,i,h为跳板，发现存在两个最优解集合{d,e,f,g}、{g,h,i,j}。
在这里插入图片描述
此时我们以g为跳板，可以发现，两边集合都可以通过g作为跳板,例如可推出最优距离dis[d][i]=dis[d][g]+dis[g][i]。