数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
2 T( V V- F6 e, _
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
, T! U" a3 K& b. n# F
仍用数学归纳法，
$ r# [/ \+ i8 k: F$ d$ q! n
假设N<=n时，弗法正确。具体值我就不验证了。
7 @/ B6 [/ ~1 B1 D$ b5 p) E
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
$ M$ E$ S9 v8 o
三重循环中，我们都把K排在循环中的最后一位。
1 T3 I5 [% e: ?0 U3 V& l) i
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
1 q( L) a/ {3 z5 C
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
: u0 U3 S# E; M4 O& B1 L5 L& ?) N
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
$ }; {: C$ Y X* a' |8 e+ _, j
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
# p6 M, R% {* n
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
3 a$ i, c- z9 w' I8 K
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
+ G5 L5 O8 h3 v# K. s8 z
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
. D0 J( @- X' i" T
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
, _& M3 ~: U4 ^: C- ^
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
9 e B; q+ q1 W$ X5 z
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
* E6 v3 \2 Q4 g* K; Z. w# E
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
8 J. U4 q- K: }3 {
这样，弗法就可以较为严格的证明了。
& ]' U- v: ~# x& {+ @9 H
=========================================
" r( B% C* J; P
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
( F" R4 q: u/ @3 S
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
+ K7 X4 @5 M5 I. F) f
=========================================
: t6 ^: a3 F. b$ a q8 l
! b4 z5 q: J( G3 v2 y" @
. [/ r* ^2 I% A: W7 ]# X* y: u) m, U
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
9 G. G2 Y2 M+ I2 f* d
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
' n/ b2 p1 d, ?% t2 e* h
/ m6 T# I# K& O
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
0 i% c8 N' H/ P
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
* P" @% F0 F7 E+ G1 K) T
这能叫证明吗？？？这与没有证明有何区别？？？
9 s" Y2 q: [# ]
# s! f( \5 q$ I' a2 X
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
6 c3 |3 K/ X3 N- H: K' }! }
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
; v, w1 h" V& H0 W# S
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
& D5 Z; h: v# }. c. Y5 |
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
8 W! B2 C& H7 @* N) f
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
+ \; r8 J1 W6 L& Y4 P0 `
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
9 E4 F8 C* L3 [7 w, P3 R, P
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
' w: s/ G% v. L
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
: `" e' T" P/ ]: \
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
! P" I& {3 F0 n
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
8 z: v$ d: M& s. T6 N# K
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5