数学建模社区-数学中国
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
[打印本页]
作者:
释永思
时间:
2015-9-7 11:12
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
本帖最后由 释永思 于 2015-9-23 16:16 编辑
) u5 X. u6 k r( A' t
0 K& h) x' \4 ~/ _* V: w' x# r
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
; v) e; _. R: K( |: }" ~. Y8 c" |& F
+ o6 T; ]% q% H0 ]9 L
作者：李均宇（李恒星） 2015.09.07
7 x; A$ R. v% Q9 s, b4 i8 Z; q
5 V# W2 F* Z+ E
我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
+ A$ l2 t( \$ H
假设顶点数为N，
# g$ q, l; d% f8 t! G
N=4，5，6时，具体的弗法正确性，我就不想验证了。
( ~ b2 S5 j/ \- L6 Q! n+ e4 S
假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
2 I4 h! J1 g3 r5 D/ m3 i
先研究下N=n弗法正确时的特性。
( g* }, m* R1 I7 i" u
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
1 q" L ~( \2 \: x
当N=n+1时，新加一点，称最后一点K。
% ?; k' X- a- j3 u1 l2 f
令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
% v2 h. [3 S; E$ T9 d2 I- [1 N7 V0 j# W
令最外层循环为k,中间层循环为j，最内层循环为i。
# T- Z1 U Y I2 k
定理一：
5 _4 x0 c5 E0 H0 u: ]9 P+ K$ [
最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
' u, L/ w: I" _; Z7 S |! x
证明：
% Z* S7 L* L* N1 T% ~$ t4 e/ g
假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
7 O3 h; W5 G- i+ w5 p
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].
* v: c, b/ U. V! H. n$ `7 \0 o
所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
; i4 j# P2 S7 k+ `. h# r# l
定理二：
t0 {) I- [8 c' c) ]* {: t5 O
最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
8 q' t! D2 I' C% X( K
证明：
9 l& f( A( ]3 U
由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
3 u; V7 W) I' V: g& u
1 O1 I3 Q7 N: R n$ c1 Y
定理四：
, e5 x6 V+ _+ `4 b
最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
' Q# c# j$ V2 P
证明：
- ?$ j1 G/ A2 D' I
k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
' Z2 F/ ^% I2 ~+ ^: Q7 q$ l
此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
' D$ h* @: }- g+ Z( e- q L
可知i,j必连通,即D[i,j]必非无穷大。
. f; ?6 U/ R% d( ?$ ^
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
7 M% O& |7 H# k6 f6 A0 v: n
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
5 e$ m: _; z+ `# R- _) u
定理五：
, Z8 J7 n: H* {7 K; E' E
与k相连已经全是最短路。
/ f. ]8 |/ l; M2 E
证明：
8 }1 l+ h. o; }/ \# |3 h
因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。
. P" a3 ~* ?( H+ R* _
/ ~0 {' ^7 E, B
所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
j' z: @1 ^" X- H6 `
所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
. f5 C) l) X9 u) X! [2 N I
则N=n+1时，全部三重循环后，全部仍是最短路。
# }9 K. X( K2 C6 ^7 ~+ i7 _
由数学归纳法知，三重循环的弗洛伊德算法是正确的。
- \0 N8 L: t+ C; Z* W
///////////////////////////////////////////////////////////////////////////////////////
, a6 J' C! ^2 u5 I& z: h
关于弗洛伊德算法的新证明：2015.09.23
( x \( B* D, [
1 m* F/ B0 Q4 T X9 g6 Q
经过弗法的三重循环后，任意两点之间的距离已是最短路。
" Q2 W# `9 f) a' M+ {1 h2 c
仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
7 o1 j0 `2 W. l" y
设k = n+1是最后一点。
) Q1 a1 a( G4 G9 ]9 c
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
! F+ L4 s" u+ v+ U
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
! Z" r7 n% F, S1 N3 Q: Q
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
# |: N/ b# E. ~ `7 K7 f
当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
3 T# ~; y; o0 W% R; e0 d' k* `* M
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
9 S3 v1 O' ?+ }; G y
例如k点连通cd，c点连通ad,d点连通ab。
. C- P* h. _' y w( ~, ^1 f
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
% x& R- O5 m z- d) x
所以命题得证。
! o0 ~6 j& M( G# c) N: b! f
* n, G4 S: W" ` ?4 w
; @ L* J' P# J, _; u( D6 ]$ r
' I r0 g" _5 J8 f0 k/ Y
9 D$ m( [4 u& a! j5 \6 \
# Y9 y C- p" y" G/ O6 @
' [1 r4 P; E; k1 y( k4 w: ]* x
0 G. M! l4 n9 Y2 ~
8 h8 @( U% U; A# j
+ ? Y( f9 l0 L+ U! U1 c
+ i7 s$ H0 i! J
) t: ~8 a4 m* p; j4 Q) |6 ^, M. L
; W6 G9 w0 b8 z8 S2 D# u# I
! o0 L6 z1 F( U- [3 P# Q
$ M) p( [% r& x" ?
7 r# ? c4 |0 @7 U
+ Z$ n/ ?- s$ I1 \4 J5 C
7 e6 [7 `) B/ o% x7 R4 A
. d/ Y9 l8 s) Z2 ~4 x/ N4 A6 |
; |! ^" [* j( h o' `
* P. W& S: `/ k. o. Z5 Q
0 i8 y9 e2 x9 V( Z. C$ O
8 u1 R [, c% Y
作者:
我的头大啊
时间:
2015-9-7 13:04
顶·~~~~~~~~~~~~~~~
- A. t3 o( Z3 I/ g5 s+ R
作者:
风靡全球
时间:
2015-9-10 17:52
加油
9 {5 G x; A! V
作者:
风靡全球
时间:
2015-9-10 17:52
加油
/ O, H& d1 n; |# D0 k2 w. l
作者:
风靡全球
时间:
2015-9-10 17:52
( Y, R$ G5 c, N& e
作者:
风靡全球
时间:
2015-9-10 17:52
加油
! ^) V( S, N3 u' w; [4 x
作者:
风靡全球
时间:
2015-9-10 17:52
加油
}. ? `- q, F) E$ W M" T
作者:
风靡全球
时间:
2015-9-15 16:59
加油努力
7 C/ F5 @1 V L
作者:
风靡全球
时间:
2015-9-16 17:58
加油 一定要努力哦
& v0 I) e7 k5 \5 o' @
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
6 z) K$ {5 g/ o0 N' n
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
4 T* I; |: i3 j- \% S- x
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
4 n- R* @2 V' `
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
1 d- K/ |! G" k+ ^
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
) X- @! S* e! ]7 O: B: O
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
2 G* ~ K8 [7 d5 W2 p" W) x8 |
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
; ^) f0 F! g4 ~/ [6 Z2 e2 t
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
% o$ G/ s+ D& y+ I1 ^
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
3 [6 [, C, Z3 z5 g4 M
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
0 w% `; `8 S/ H( G
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
! V, t* B1 ~' W* J" C) r1 O; A# [
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
6 r! k r4 U9 Q8 d
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
. g% P P4 f/ g- R1 f
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
0 B) R' _& |" }6 i# }1 r
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
0 H- N. s4 n( G
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
& h. O- i+ i3 q% S! `8 E
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
( \, u" R# _& Q( g: _
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
8 K; e9 u: z# W
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
6 f) L, f% |0 c+ v
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
5 g8 O( U+ Y0 m$ e$ L6 T* _: q0 Q; M) |
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
! W+ K) e% F1 e: J; z4 W! G
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
: M3 u7 b/ ^/ R7 e
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
. ?$ M J/ a- x4 u
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
9 V7 s% m" `# M& H ?9 I7 e
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
