最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程

释永思

=========================================
: g- j$ p! @" e. w: Z5 G5 F, U8 y最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
, V0 J! i, s9 F0 p仍用数学归纳法，
0 G, g/ U0 t% _: _$ X8 k假设N<=n时，弗法正确。具体值我就不验证了。
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
三重循环中，我们都把K排在循环中的最后一位。
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
1 a5 Y% y* D! Y* D0 W- Y; f! y8 B如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
7 w9 @( w$ X) Q8 q  _' }3 O' |那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
+ n' O  }  B/ m" W, ~由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
0 p$ u9 F8 T1 W1 Q所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
这样，弗法就可以较为严格的证明了。
9 }, k! c* C1 G( z$ R: A, N=========================================
  M4 J# w  n' g0 e* ~  T为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
: E1 ]$ h" g% z+ v  V=========================================
3 ^. W; k! E  J  a% {5 W% d

/ G7 a  J5 q1 `4 b$ v

风靡全球

加油  我们支持你
& I9 a3 a6 e! G7 c' Q1 `* v

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你
; l% [9 w5 {# C! i$ A) s. d- W

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你
0 L  F; w% p! ]

风靡全球

加油  我们支持你
. [# Z+ D% i$ @3 Y# K# z) j/ d

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你