Floyd 浅显证明

Floyd 的思想是枚举中转点来更新其它点，但它为什么是正确的呢？

证明：

有些人不清楚 Floyd 正不正确，其实就是怀疑这个中转点的遍历顺序会不会对答案有影响。

那我们先提取出两个中转点 \(k1\) 和 \(k2\)。

• 先让 \(k1\) 当中转点，在让 \(k2\) 当中转点：
  \(\quad\) 那么对于被枚举到的两个点 \(x\) 和 \(y\) 来说，\(dis{x,y} = \min( dis_{x,y}\ ,\ \ dis_{x,k1} + dis_{k1,y}\ ,\ \ dis_{x,k2} + dis_{k2,y} )\)

• 先让 \(k2\) 当中转点，在让 \(k1\) 当中转点：
  \(\quad\) 那么对于被枚举到的两个点 \(x\) 和 \(y\) 来说，\(dis{x,y} = \min( dis_{x,y}\ ,\ \ dis_{x,k2} + dis_{k2,y}\ ,\ \ dis_{x,k1} + dis_{k1,y} )\)

$\ $

所以说都是一样的