数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
$ t! \' C' v( h" }+ ]2 E( r; V) D
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
/ h0 V \7 ^# x2 E# ~& Z
仍用数学归纳法，
. J: J, Z2 a4 q6 q, L% o/ m
假设N<=n时，弗法正确。具体值我就不验证了。
; W, z- k! z* s2 W# A0 Q8 f
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
) ]- Z" ^. v, W' W/ l N W* R
三重循环中，我们都把K排在循环中的最后一位。
. S! Q- J) X! r# h: Z# }
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
+ I. [, a, R8 @! b+ g
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
* B. ]7 P3 E4 x6 E2 S; v
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
. {7 m4 w1 M8 Q4 h7 P
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
5 p- ^( z: t% M
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
) q+ h3 s' v U6 |5 v- V
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
3 P. s+ G8 H6 g, `! K7 F
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
8 E/ ^6 o$ F4 @: A
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
: }/ ^. @! e9 x: Y$ D, U0 n
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
: `8 U& C1 z3 ] {
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
1 o6 ^& v& o, A- k& }6 w
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
, V3 b4 L* R2 j0 n9 j8 [5 N: Z6 a* k1 Y
这样，弗法就可以较为严格的证明了。
! ~! i$ X3 X3 Z" Y' x0 |
=========================================
p! j1 n0 v+ {% Y2 G; q* W* ~
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
& {7 x; u1 s$ O9 R+ G# J
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
: Y" k/ T$ I1 s- S0 V. I0 b$ ^
=========================================
, ]$ Y, {$ \* ~4 g" T C5 h, V
1 \# u0 g. R( q5 u
) R* t6 l3 e+ Q$ Z* F* t2 I9 {
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
- z+ x6 I8 ^ @; b; Y
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
3 S4 |0 L: K* y) C/ Y( m- p! B
8 o! H, Q8 S8 K1 F: m( a
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
% Y$ V# C/ C) `9 d4 F& i
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
1 `/ o" \% a: v3 w
这能叫证明吗？？？这与没有证明有何区别？？？
; O, Y+ P9 Y: }% x1 V
* H2 g% M: A, n' S- C" L! {+ z
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
9 ^5 ~3 a/ s/ A# H& c2 m
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
2 Y2 J* I/ ^9 P }* c7 \
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
, p- _9 C5 k; s: u$ s
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
4 O) r5 h4 o% T) f8 H/ U
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
% {, y1 S; ?& j5 W+ T; d4 ?
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
0 ?/ f! j7 \. f* @% {' W! C
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
p) G' L* }4 ^5 f Z7 v
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
3 s2 I$ f* C, n) u4 a- R$ W( k; ^
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
2 P( p; z8 _' T/ V6 D ?- e
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
) |( O; A! G, v$ z2 q
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5