数学建模社区-数学中国
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
[打印本页]
作者:
释永思
时间:
2015-9-7 11:12
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
本帖最后由 释永思 于 2015-9-23 16:16 编辑
+ {" W. Y9 A+ u- Q1 S4 W6 L% T
5 y, I+ n5 T' T7 C4 ~" m
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
9 f% j! D: N- G9 ~. d2 w6 h
. w( ~/ w! _2 v+ c
作者：李均宇（李恒星） 2015.09.07
( H5 G2 M# |! B5 y
; a |) l' i4 m/ K0 A5 g
我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
! f+ D" j9 V* ~6 ]% ?& b( ~2 X
假设顶点数为N，
) L$ x5 w) m. f1 D3 K9 S% ?. I
N=4，5，6时，具体的弗法正确性，我就不想验证了。
; {; ~; s% j, O( V
假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
) A4 o) J( E6 p) j8 R* n2 m
先研究下N=n弗法正确时的特性。
0 R7 \& f) t! e( K3 y
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
. B$ ^ `8 U5 q9 {6 i! e
当N=n+1时，新加一点，称最后一点K。
- ?) S2 e+ G2 @0 g5 {: w5 D/ s
令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
& T9 c4 `( }* t
令最外层循环为k,中间层循环为j，最内层循环为i。
1 \& X# k* r9 e. G4 g) R/ ?
定理一：
( @4 f# c7 o- F: o
最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
. R. n/ y5 T, g {% l3 d! T
证明：
5 }" o) r% c7 `* q- B& k7 V
假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
4 E' D4 ~* }2 ?
D[i,j]已被替换成为了D[i,k]+D[j,k]，而D[j,k]+D[j,x]>=D[k,x]或D[j,k]+D[j,x]>=D[k,x].
/ ^5 o4 i; u5 H7 E. P" {3 z
所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
+ U( ]; k. @/ x; T2 m9 c
定理二：
. s8 E) |6 g5 G) F, i: R
最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
1 s1 ]7 o$ K L" A8 @) {
证明：
: R$ |1 A7 S' Y5 ]6 ~5 q1 I5 ~5 }
由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
( k+ T W3 w0 A% q$ H/ S+ C
/ X: o9 ` C2 B/ k5 L
定理四：
0 Q3 m8 |+ z, E6 q$ p7 E
最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
; a: i7 A: c/ ]1 b" b6 G
证明：
% `& ^* w8 _1 |$ j% {0 E
k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
F! g* k/ x2 V3 H& F! `
此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
% b( r# a Z/ h
可知i,j必连通,即D[i,j]必非无穷大。
/ a1 c1 A3 F% B
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
3 O' P* U O2 q; p5 c( E8 p# ]3 f
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
( k a; V/ e. m
定理五：
; U& r: k8 D" F0 ?3 z |! K9 Q
与k相连已经全是最短路。
: _/ Z- t9 `5 @4 H9 L
证明：
. q: e6 `" r' u
因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。
3 A) p; m1 J4 g1 H) d
: S+ h4 q- d2 T/ w
所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
; O* Q* L# {1 e- Q1 K( L2 _
所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
' s# {4 A( p L$ L$ M0 W
则N=n+1时，全部三重循环后，全部仍是最短路。
6 D( q7 J7 G" U' j2 `
由数学归纳法知，三重循环的弗洛伊德算法是正确的。
9 L! i* C, R% ?
///////////////////////////////////////////////////////////////////////////////////////
: s) c+ d; N+ h7 o
关于弗洛伊德算法的新证明：2015.09.23
+ u" I# S9 `# f: l/ i) c
* f9 W" A8 @ j3 P
经过弗法的三重循环后，任意两点之间的距离已是最短路。
# l, x" ^, Z) w6 x) Z7 r2 E6 Y
仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
4 m* C/ Z5 W4 p. k( q
设k = n+1是最后一点。
; o$ c* c2 }/ [3 s" z8 Z! d' }
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
; h$ \5 K' U- @& D4 I8 d) Y% t
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
* c* O5 T# c5 @7 E! H7 A. j
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
9 ?5 W4 s/ ]0 ^# `$ T3 \7 G! u0 |. O+ H
当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
, b$ O( b/ y1 H0 z
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
: u" r) \6 q7 _- g! \0 k
例如k点连通cd，c点连通ad,d点连通ab。
# ~% u2 m1 w9 D6 R
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
$ w4 H4 g6 w# D# Q% t' T& ?/ Z% B
所以命题得证。
$ M6 i) [1 K6 S! Y/ m
' f( {: Y0 L8 W
" y) l' @& ~) p d7 b
4 R- p7 b- q* Q+ w2 J/ ]
% z" t7 \$ P$ a% \' |5 b1 _2 N( ^
8 G* B* c4 `1 e# E5 {! k
4 J/ x1 n8 X2 I4 X6 v& s! a
7 s. q, J- T5 c
9 [8 d& U7 [4 ]( w$ n
( n4 n2 g# j. l* y/ _
\- H, G% S6 x8 j: I |
* k2 W/ c* c r1 s5 f0 j+ h
* |; M# o; {+ I4 l
% z2 r# l& S |# }9 B
; U5 C" G& E; M6 F* M
3 S- `$ l8 N1 m/ [6 Q$ d
2 q6 @: ?. H7 n O
i% a# u, c0 p0 q' r! B& g
3 J% T7 |; ^9 I/ F2 e
& ^" [7 {: |3 g. ^0 _
) e' O. c6 n, ?$ P4 q2 O$ m- u0 X
9 W9 N+ i9 {5 }3 x% e
, U' {/ p. n( |- V+ H" u; ?
作者:
我的头大啊
时间:
2015-9-7 13:04
顶·~~~~~~~~~~~~~~~
0 A' u9 s; [& \7 r, X/ H
作者:
风靡全球
时间:
2015-9-10 17:52
加油
" D* _: m8 J7 P2 s7 _7 ]
作者:
风靡全球
时间:
2015-9-10 17:52
加油
! F+ ^5 V8 E! v: o/ T9 V
作者:
风靡全球
时间:
2015-9-10 17:52
( z: q; f+ w3 W
作者:
风靡全球
时间:
2015-9-10 17:52
加油
' A, u9 H5 e, {7 v! S
作者:
风靡全球
时间:
2015-9-10 17:52
加油
! d" d3 ?2 J' e) q7 u* p+ r
作者:
风靡全球
时间:
2015-9-15 16:59
加油努力
$ n4 x* w0 g! v6 g
作者:
风靡全球
时间:
2015-9-16 17:58
加油 一定要努力哦
& Y* ?' w' [. I0 j: c$ `
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
B# J" A7 G# F4 p. O& ~, \
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
. W1 G$ m$ i; X9 ~+ e# v
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
3 t. Y# p+ X) |5 o5 v# i! M+ w
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
1 d+ G a6 t9 ^+ a, m: P
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
' o5 n% T" t9 c8 E' x2 C7 F" P8 U
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
! d/ [$ F8 M' X" c+ u2 _& r
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
: w! a; |0 e. q6 D( H: }$ M) W
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
) H' R. l1 A6 [0 v
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
1 p* K2 j3 g6 x/ L% `2 y8 S9 j
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
3 v* P4 ?! ~) U7 I
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
+ C$ C. @" x% e* m: P6 W# z4 q
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
3 g; n/ y+ K, P$ G7 c" x
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
+ `$ \% z+ s$ w9 }" z
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
% Q& A# A& p7 J+ \5 y0 n: f3 A. j# Y
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
. Q9 b+ T) E# n% W" k/ V H
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
- X# ~4 ]# u4 d. i% T' q7 m
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
% G( u0 @& s8 O& x
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
! L8 U( M1 C! M- U' Y
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
6 v/ V4 E1 R1 x( P) G) Y
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
2 g4 e) c* k8 ^" m
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
4 ^# E( a5 h( @6 |2 h, r
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
1 g% ^5 ` d: x8 i$ K6 z
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
8 p; @( k! B" v" X! C
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
/ d$ y8 |2 p8 p1 N5 u
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
