数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
5 ~- _) C( u, X& i! |6 ]0 T
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
# [, w% |- Y1 p) Q- p
仍用数学归纳法，
4 O) G- u2 J; L: T6 \+ H
假设N<=n时，弗法正确。具体值我就不验证了。
- r* ^# E- _9 }) W# C; ]
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
$ B* b7 D4 D" ? ]8 d1 N. J
三重循环中，我们都把K排在循环中的最后一位。
8 C( S+ D( N: a
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
& S2 e7 ]+ u% C* N3 _
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
n" |. G5 S- u' K
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
/ z* L* P, P& [
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
7 D/ f0 f) P1 f2 a
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
) |- p1 s* B$ m
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
% P+ s a6 [0 R4 j5 v
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
2 @. w5 T" E6 W2 q/ N$ X+ F
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
. f7 ~, z$ g8 X+ [
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
2 y# C. `& X$ _0 S; o9 Q( _
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
% m. S( e$ q. t7 b
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
" h. G2 x5 }; m' X4 t! R
这样，弗法就可以较为严格的证明了。
/ x) w( r f) q0 Y
=========================================
0 }. i! ?' a9 Y- s) g
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
+ t4 v8 i5 P* _7 k; e' f
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
3 y+ w$ T. C% _9 a- P+ P6 v5 s
=========================================
: e" t8 z% V. A+ s
- w8 G. r7 \. t0 f# ]! i( d% ]& h8 ~
; k% f, o% m2 X5 P! U
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
2 Z. c. K- y5 [1 b
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
; p9 n2 F4 W9 u
( j* f- Q/ F( b8 \5 g: h6 v6 N) T
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
( p# n9 ` w2 R4 d# H) D0 p" f
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
5 v/ k0 R7 {- D% [' [7 q' L1 J
这能叫证明吗？？？这与没有证明有何区别？？？
4 @( s* H* V3 g! X w
}% c5 x, W- p: p5 u; X4 E
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
8 p9 Q; E _. c& [( k$ J7 V0 {/ @
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
/ g( x3 G6 M0 D2 _4 e* C
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
% d6 |% Q/ \' M! @. i; H
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
% s, p8 W( }' k; q7 j
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
6 q+ t( X& a! c8 t; v* }
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
. K& g5 k. W* Y8 v5 S8 t: Z# O
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
3 B& r# f8 ]4 [0 @7 v8 }0 Q
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
% \1 b8 n) W D& Z
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
; w/ i! ~3 n& M0 H' ^7 t3 N2 n: X
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
0 p4 I. Z% A) V/ \1 w
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5