数学建模社区-数学中国
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
[打印本页]
作者:
释永思
时间:
2015-10-31 13:45
标题:
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程
=========================================
/ K! ? g1 Y1 k; V8 b% h2 r( k- z
最短路径中的Floyd算法（弗洛伊德算法）的较为严格的冥想证明过程：
: S/ o: N, G6 ^- W/ x
仍用数学归纳法，
& b! _. P# H/ x0 a5 W# n
假设N<=n时，弗法正确。具体值我就不验证了。
+ u$ e. Y" s. ?) x9 W1 M* w
当N=n+1时，假设最新一点最后一点为K，此时K=n+1，
( \. D# j. X* d; f8 e3 |
三重循环中，我们都把K排在循环中的最后一位。
7 _( \3 ?0 q% ?7 H' v! |
现在我们要证明的是，加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
# q: |2 Z- b; x; P1 u: p; o; I
如果原来的n点的某两点之间最短距是与K点无关的，显然经过三重循环后，就是最短距了。
3 J6 {* C' G' z q: Y. O# S5 W3 P
如果原来的n点的某两点之间最短距是经过K点的，假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距。
% ^) M- B) ?% e) w
那么由弗法知，P1,P2,P3,,,Pk-1与PK+1，，，，Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边，不是虚边。
. a) }, E; |3 _3 h; F0 l
经过最外层最后一次循环的松驰操作，必能连通P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
) k0 m; r, T+ H) ^! t" @& c Y
所以得证：加上新点K点后，经过弗法的三重循环，原来的n点之间仍是最短距离，但是n点与K点之间的短离是不是最短的就不知的。
7 i) y: q& ]2 j) b1 u/ N9 w& U
由于对称性，将K点置入内部，把P1点放到最后一点，原来的循环结果不会变的，
8 P& t) p" m/ U, S0 g, s
所以三重循环后，K点与原来的点（除P1外）的最短距，就可以求出来了。
9 [' c9 g& q G8 p7 Z: r3 g' [
由于对称性，将K点置入内部，把P2点放到最后一点，原来的循环结果不会变的，
% E N& w. {: f/ q* I1 d$ H' Q/ u
所以三重循环后，K点与原来的点（除P2外，但P1不除外）的最短距，就可以求出来了。
; L9 b5 y; B/ q, N) g1 j: V- w
所以K点与原来的n个点的最短距，也就已经求出来的了，仍是原来的三重循环也。
% e. f% g4 Z$ p7 r/ _* O6 @5 X) W! l
这样，弗法就可以较为严格的证明了。
- K6 }7 c! o% F! h, ]
=========================================
+ {- G) K8 c- {, J8 B
为何假设P1，P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距，不是虚边最短距？？？
5 ^) \0 v. U' G
如果是虚边最短距，也可以转化成实边最短距，然后结果一样的。
* t% S* b8 {/ H
=========================================
1 G" v& G( v# s3 d! i
- Z% G6 q! O& I$ \2 l; f
) C/ b- i$ `; c% x( ~9 w' I" d
作者:
释永思
时间:
2015-11-4 14:03
忽然想到，上面的证明中有一点未严格证明，就是，要证明弗法的三重循环与N个顶点的排序次序无关，例如for i=1 to n 与 for i=n to 1等次序无关，我没能证明这点。现在十分疲劳，没有余力思考这点。
: }7 J0 J7 s3 W* E1 [& |) e) ~4 Z
作者:
释永思
时间:
2015-11-5 10:47
谁人能证明弗洛伊德算法的三重循环与循环中的次序无关？我没有余力思考，我太疲劳了，我也不知如何证明，求助了。 例如要证明弗法中，for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明，用数学归纳法也一时想不出 来。求助，我太疲劳了，要休息，一时没有余力思考研究。这个也是我一时想到的，弗法无边，永思不尽。
- u! D% z- M& ~, r8 o
! S. i$ k- d1 E W( B+ ~8 [
作者:
释永思
时间:
2015-11-5 15:16
弗法：数归法：
% t- f6 Y, X' j0 |* |7 ^0 P, v
对于N<=n的任一个混排序，K点替换其中一个点，必也是成立的。这样，就证明了弗法的混排序？
' _' j- P: T$ G; K3 w
这能叫证明吗？？？这与没有证明有何区别？？？
* L$ v/ n9 y8 Q7 a. @/ A
% ?0 `. `0 `$ d. K) c
弗法中，必然殊途同归，归于最后唯一的最短距离，这是唯一值，不会有多个值的。所以与顶点混排序无关乎？？？
2 E$ @1 A1 h3 V2 O; g: l6 W
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
( J% ~1 f8 l- ~& O4 I+ j
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
6 R: K( i; k( p- G' k" s
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
" U R6 u* I3 n+ C
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
) q3 `% ^/ ~0 U2 y' e9 {
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
% v$ V. Y! J0 A/ j% R
作者:
风靡全球
时间:
2015-11-5 17:47
加油 我们支持你
& J+ ?$ Z. r6 x& _& p m, e N" h7 Q6 `4 ^7 i
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
) d: w+ F5 F# O5 K, n) U
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
# ^% ?1 v% I+ M9 E2 y
作者:
风靡全球
时间:
2015-11-5 17:48
加油 我们支持你
/ h+ T/ W; k& y
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5