数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
3 o9 J9 d- h. n# W+ n
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
' h0 l/ M7 Q/ s, c* s/ {8 Y: F: r
仍用数学归纳法，
; C) V3 l0 y' r$ b
假设N<=n时，弗法正确。具体值我就不验证了。
& ]) B4 R" H0 x
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
6 G* u; T; R. D$ Z' A
三重循环中，我们都把K排在循环中的最后一位。
) } b, U6 }. O p9 i/ X, j- [
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
6 m$ Y% |+ C/ Y$ l
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
) d0 Z9 m* D& N C* u
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
+ K+ `" Q& z4 Q( P
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
, ]& l' V. D( b$ s
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
Q; G+ {& }' C" u
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
1 G# ^, b- g4 y5 E! A
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
2 V9 l, s8 \' c0 _" A8 ]/ O
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
. _ i3 H5 n/ Z
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
7 x2 k0 A% ]+ i) g. h8 U( K4 L& v
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
7 f3 \+ ]9 Z; M: A
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
3 g( m. e( }7 o4 o9 j. g. G. Y
这样，弗法就可以较为严格的证明了。
! v, F- F" w, z
=========================================
5 C3 |" y, a) E5 e' G' `% ?
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
) _8 o% Q3 H, y" ~0 |* J: U q& `
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
( A9 ^! y8 ] x% s/ ?% M. d8 X
=========================================
8 A. r/ ~; i" O- X
% k% U+ _5 t ?- x
1 z7 r) a8 }/ |( \6 l* {
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
6 J; Q( h C+ i5 H$ j# w
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
$ \: t2 p9 Y4 w$ B7 a. G
: I7 s) _) i) N; _# o3 |% L* F0 t
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
* J5 |6 }; Q, P+ z- |
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
- ?6 t; H: m; q. P
这能叫证明吗？？？这与没有证明有何区别？？？
& S+ z+ ?$ n9 L1 T
/ h. ]1 W- `, ?3 G) Q4 T! w
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
2 l& K8 [6 V: H& `% y4 C) u( {
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
) T. T8 t% j+ ]( O) r
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
8 z4 z- {; r( g' H. h
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
8 p/ g( W& h( g' I! C6 x6 N9 Y( U
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
6 M4 f1 _) m1 K# r
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
/ ~; n# \* C0 u; [0 S
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
0 k7 m3 U7 S5 [; |7 A/ v
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
# B O, O' G$ z
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
6 v7 |% P: d) N) p: Q; Q0 _
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
# y/ R9 y" H* t. ~. x/ N/ k4 D9 `
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5