数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
& C7 A. I. ]) G' T
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
6 J5 o7 J/ [0 m% K: j
仍用数学归纳法，
# w- F8 r+ L! ?
假设N<=n时，弗法正确。具体值我就不验证了。
; T6 [, U+ s, N+ G7 q; {
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
3 j/ N8 R7 ]# T' t, c4 o7 i
三重循环中，我们都把K排在循环中的最后一位。
9 W {; j8 f8 B5 i" p" b
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
+ t1 @, j! a& [/ X5 {8 g( c" a+ \
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
- q4 g& D3 N4 o) k
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
& i, u; O- }# ]- {
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
5 U$ J) V6 F+ {" O9 v
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
2 U0 ]7 ]% [8 p! n H
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
7 A) F( `& W l/ o4 l- x/ p; J
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
5 M: R* T3 `& M" N P6 n% p( X7 B
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
4 g0 E0 z* ]5 z" J/ P2 z
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
0 k/ b& s: L7 J; M V
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
2 ? V7 V0 u Z
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
. n. v4 A) z6 Z* ]# L+ B# f/ s
这样，弗法就可以较为严格的证明了。
! b2 ~: g4 h8 T$ q: O$ j
=========================================
# k! x' R9 U+ |/ W& \& b
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
% h6 _* e( D1 a) R& i! e
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
8 d h, b6 u! ^% l7 J! m
=========================================
+ _" _9 m! @7 |' N2 D/ f2 ]: t5 A3 G
- c' j; u' s9 |, T9 u0 N
% u7 R1 ?! c( B9 h! |3 C
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
3 |" L. c9 I8 V, p! I
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
' k Y3 i* i$ w7 |: @& h; z: B
2 @% k1 m) O9 Y8 L
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
1 m( j& C6 A1 }- O% B- Q0 |
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
* z2 _( r: V; g4 A$ L- G f% f9 n! j
这能叫证明吗？？？这与没有证明有何区别？？？
& }: q1 E( @( c( }
8 o9 H& M$ L( ?$ s% k
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
" u; _3 `( i/ T2 j& L! A
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
' C$ A0 U9 @: Q, |) |% F- g
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
$ C, ?% y0 W" `- `, {2 K* E
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
; c8 x# Z! R0 x+ F; U( {
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
; O' _- K6 Y8 }( K
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
, k; Q! v6 A* O# ]% f- U
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
" I! P7 c0 I- _+ u% D
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
, R7 X* }3 C& t* P
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
* H2 L1 t5 b2 |1 F
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
8 \! d' p8 F/ d) L+ L5 `; B
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5