数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
* P+ b. R d# u& a
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
: g" z, m. V9 z$ Y" f# O2 H+ r
仍用数学归纳法，
: I/ ~. H! [7 @, x0 U2 u
假设N<=n时，弗法正确。具体值我就不验证了。
; X7 X# x3 ~, i. C/ X, K
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
1 K' G4 c' `% Z2 g0 \3 o: \$ Z0 g
三重循环中，我们都把K排在循环中的最后一位。
: z9 p! c/ T/ p, i1 ]3 m( l
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
8 q0 V6 C3 T3 A8 \9 b& b
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
, c$ j5 {0 V% Y9 j5 A' I2 T4 X
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
+ u8 F! ?- w2 a- x Y5 g4 R% B
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
. k' C: o5 i7 r4 z4 ~4 }) o+ j! i
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
/ G& S5 q& u9 l+ q+ B
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
- N4 a- X- w1 D- l, |# b8 c
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
( x; J$ V( U3 V& m) u5 r
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
+ G; F& M4 {2 P2 O
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
4 n _( D) F: O* s# E6 Z+ E
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
- F6 j( S0 k/ e; n* I- m
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
: W0 I2 I1 j$ s9 E' M
这样，弗法就可以较为严格的证明了。
" I5 {; E& k/ r5 ^5 {
=========================================
3 B+ K& {" l. @- _8 n2 J7 ~) }
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
$ K$ R/ k5 r: U0 F: {
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
4 J: u6 D2 |: [& Z7 B
=========================================
( {% E4 s' h2 i) g9 h9 H8 p
! P* E1 w( t3 t9 u9 X! k
/ c5 ~" Q5 ?$ g5 ~
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
3 y( f# L- y& X$ T6 b1 F
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
+ t8 ?# Y8 u$ j# `/ M' J
* `# r+ C! o7 |) Z3 n8 B _
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
: r2 J6 o& h0 i5 G/ Q( }
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
, o, G' j U# d
这能叫证明吗？？？这与没有证明有何区别？？？
; }! C: Z2 C8 Y0 {: }) y
4 T( i- b1 ~( z
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
- ^+ p2 i* S# v" L- Q! d
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
. c2 L+ Q3 q( M, X! g) A( H V
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
6 K( U6 T: j3 y" F5 Q
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
. I* g" C. o* X, N6 k
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
3 A- y9 N& d! a6 q& A$ z
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
% F, I+ H- L0 Z/ Z9 V
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
. ?: b. M$ U8 I u
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
9 u0 b1 a" c% y5 W) x
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
7 X* X9 a( W; c9 z. L" C- w- ?: [
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
0 M) E! h) Q! m: e$ r! Q
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5