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

释永思

=========================================
/ |2 N0 l& }/ e2 D3 K0 t6 V最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
仍用数学归纳法，
假设N<=n时，弗法正确。具体值我就不验证了。
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
* z4 Z: C  ?$ V- C三重循环中，我们都把K排在循环中的最后一位。
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
7 f  b( Z, b  U! f( X如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
! {  P; g0 z4 k, J所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
, D3 l; o) u  N2 q) n1 h! x: @所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
- W& n% |" g) l2 z6 W由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
* C" Z# E( j- |! u% L/ |' _+ w' _2 y所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
! W* {# u8 q# v- _  a所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
% p& v4 x) m% z7 E2 d3 ]& \+ p7 P9 z这样，弗法就可以较为严格的证明了。
+ h; u3 Y2 J  a=========================================
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
4 |/ K7 {, Y8 w9 x4 j0 r如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
4 i% g1 R+ ?- ~4 m/ v" i=========================================

6 E2 e0 H7 Z4 m: e- W% w
+ f3 G) |( N" t8 |: @

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你
6 @7 _2 ^1 i* b' Y" I

风靡全球

加油  我们支持你
# ?( p, F  |, U) X

风靡全球

加油  我们支持你
1 _9 D' [2 N% X5 u- {* e

风靡全球

加油  我们支持你
  e9 `4 K' F, k9 j7 n