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

释永思

=========================================
* M/ m0 i2 g5 s6 _- |! G最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
; [- s0 d2 U% e1 J# e. ]仍用数学归纳法，
) _  U7 Z8 K9 z假设N<=n时，弗法正确。具体值我就不验证了。
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
6 j% `2 G, J* j6 R+ I$ R' ~$ @三重循环中，我们都把K排在循环中的最后一位。
5 ]7 V0 p, Z/ r" S- E现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
* w1 }( \$ u1 [# t4 m如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
7 n% v+ j: H! }那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
! L5 M0 _) I) a1 u( O. U所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
2 Q* [9 I0 H1 x- o* P! ]3 P, U# s$ D由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
/ j+ n0 i- s# ?$ l& D3 S# d所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
' P" ^% y: _2 @% _所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
这样，弗法就可以较为严格的证明了。
2 R/ m5 |8 w; P: y$ d9 ^=========================================
) D6 t4 O3 y% R为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
6 X# t& J0 x. b6 `=========================================
) N6 X: T2 J) t6 D  r( b; h  F
' l2 a- Y, ^; o# h1 s6 \5 `
2 Y3 O+ E( g& R2 X2 ?( g0 L, y

释永思

忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与  for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
. T( L) o# J* L6 r5 r% D! C

释永思

谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
" p1 m; m3 c8 ^1 O! d5 \/ y. N
7 G: Z4 D; m& d* p

释永思

弗法：数归法：
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
! i5 t1 I( ]1 B) d9 G+ }+ d这能叫证明吗？？？这与没有证明有何区别？？？
9 ^) D0 k( N) D; b) L
, A" q5 g8 e! |3 u( W0 X弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
/ J5 e  O8 Z2 n) y0 ?

风靡全球

加油  我们支持你
1 o; Q/ w: d8 |+ y3 K3 F5 p

风靡全球

加油  我们支持你
, M6 |) {3 |; d( j  k, F. R2 L/ F

风靡全球

加油  我们支持你

风靡全球

加油  我们支持你
$ H/ y$ Z- I# q& V. _

风靡全球

加油  我们支持你
0 a! H5 C0 y. }$ [4 G

风靡全球

加油  我们支持你