数学建模社区-数学中国
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
[打印本页]
作者:
释永思
时间:
2015-9-7 11:12
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
本帖最后由 释永思 于 2015-9-23 16:16 编辑
9 Y, B @7 W0 ]$ I' y
2 ]- M' s% f! ~! w! D: k# [! ^
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
3 q5 ?8 f6 L+ |0 v, X; C7 _# D' j- w
& s4 U; \6 O z9 D3 b
作者：李均宇（李恒星） 2015.09.07
/ y6 i) E2 q7 j3 {0 y ?
# x( ?4 c% v, R/ k
我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
( _0 r9 z8 ]: c9 N
假设顶点数为N，
2 d" [) F5 M1 A
N=4，5，6时，具体的弗法正确性，我就不想验证了。
) g3 m' k {8 j
假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
& F" j: w( e0 j8 b' E5 P( h
先研究下N=n弗法正确时的特性。
: a/ D6 n3 g- v- f9 W' U3 F
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
0 @% T- f: {5 n- d% p: O
当N=n+1时，新加一点，称最后一点K。
" {- Q/ c4 u2 K/ b0 F
令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
a% v6 i- Z1 }% Z: Q" x/ U6 i+ S
令最外层循环为k,中间层循环为j，最内层循环为i。
) \$ i8 ]9 }1 m) N4 o8 w
定理一：
' r5 q+ N3 L4 Z/ G5 E) O* @
最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
2 R6 ~5 _; u3 a0 n% R" n
证明：
2 X! K" G4 L. m8 [+ Z& D7 A! ?
假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
/ p6 _% I" S1 H0 J9 D
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].
2 U0 S2 m. V6 ^+ i V# @8 p8 c
所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
[- z, I" X* C. z4 j1 d
定理二：
' Z' [( d% f# S
最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
; m& t" r4 c% p, l8 f
证明：
! T3 D1 N) `! S# m) u/ S' X5 v* U! _
由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
3 l* q3 i0 K, y& |) |
" M' q- x$ G" O: o% `4 S
定理四：
0 I$ G0 o1 r* u) N: ~" l
最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
6 O% l3 g/ V& W* f; g0 B
证明：
0 W) ]8 K7 j/ {
k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
3 }# e. A. P; V* s' Y7 L
此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
8 n7 Y4 R4 K. W: Z9 D
可知i,j必连通,即D[i,j]必非无穷大。
" f9 U3 d# q6 Y( O, U) |4 c
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
6 C9 M% a; n9 S
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
2 k; _; ]( k3 A; ^0 D0 T9 V
定理五：
- u- W: M" u/ c0 N; Z7 Q. h+ s. P( q
与k相连已经全是最短路。
* B2 `' B) t% Y& t8 J2 o0 V
证明：
; d& K% n& ` s Y8 r$ f* e
因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。
: |" y/ g3 M* ^0 ~$ x
, u; A0 Z- b9 q! Q# q' t; v1 e
所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
% P" Y6 C; K: b, N7 r* p
所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
- y( P" N) O* ^+ }! C- g( J
则N=n+1时，全部三重循环后，全部仍是最短路。
) H+ ]' L4 Q! k8 u
由数学归纳法知，三重循环的弗洛伊德算法是正确的。
; E- m$ B) Y6 v) o0 L4 } b
///////////////////////////////////////////////////////////////////////////////////////
# _7 r* Y! J, q4 i& N- D0 k
关于弗洛伊德算法的新证明：2015.09.23
3 N9 h( g" W$ Q! N; r6 C
+ [. D% u4 X! r
经过弗法的三重循环后，任意两点之间的距离已是最短路。
' t+ ]% k1 P3 k7 r
仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
9 }$ t) }8 E9 e. U
设k = n+1是最后一点。
$ f1 n- N4 k% @0 R+ f5 V
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
5 T( H4 U/ ^% }# a5 {, s
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
: `! O! y0 F" X, M u# y2 }
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
; x* [' ~3 @1 A2 \1 u3 i
当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
) C: F: T! ]) H% A0 i. U2 f8 k9 q
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
Y! M9 C' P$ z
例如k点连通cd，c点连通ad,d点连通ab。
1 v4 B1 U0 V3 }. s" [6 H3 A1 d" p
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
' ^6 _% z# x) U+ q
所以命题得证。
3 S% Q1 K, v" B. W. y
! w9 a d u E" C) E' m
) i, V( F0 w* V
e+ a7 Z2 ~: @$ n# C# D! k
' G# c: }8 W" n9 M- Q6 {4 _ C
7 \! f( X- R: E9 ~! i( C" @4 Q6 {
' |! `2 U* G: a; y8 s
) P6 m; F( J2 P& X0 T1 a6 |7 o
4 V# L6 u2 f0 V2 N0 n( T
9 z, t* M, @3 m
- R8 i- ^/ ]6 N& `) d, T( a/ o% c
: k# C* ]" W3 B8 ~
n8 i! P+ n; t6 ] F
9 n% R% j2 C( Q/ b5 A2 u Z5 e6 j
& [$ c7 ?' }. L& i. B. X( H
( M S+ h0 U; a4 Z: I
- R5 S' r2 {6 d- y' d2 f& Z' r; `4 O
% j8 _* c7 x- N9 b- J0 q+ d
2 J' s& }$ Z! G
* l0 G3 r0 N4 u& n
4 P& I& t- H) U* _1 B y
. \1 z& b- U6 b W0 f+ c
6 e( ?8 `" p) ], o! X* O" F
作者:
我的头大啊
时间:
2015-9-7 13:04
顶·~~~~~~~~~~~~~~~
4 T! ?* B& w# k
作者:
风靡全球
时间:
2015-9-10 17:52
加油
2 h7 K1 S' U( x2 p9 w% p
作者:
风靡全球
时间:
2015-9-10 17:52
加油
- ]4 O8 `( M4 D
作者:
风靡全球
时间:
2015-9-10 17:52
0 G+ @: S/ L( m
作者:
风靡全球
时间:
2015-9-10 17:52
加油
5 `5 y% {, x( \# ~) B3 a
作者:
风靡全球
时间:
2015-9-10 17:52
加油
' ?3 y& T S E3 P% E( {* k* ]
作者:
风靡全球
时间:
2015-9-15 16:59
加油努力
1 w& M' C1 u1 v0 f" ^& D
作者:
风靡全球
时间:
2015-9-16 17:58
加油 一定要努力哦
! F3 {7 `2 Z3 @" B
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
" ?1 v5 M9 H- @, c
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
: z' \& d" u. f& Q3 r6 m7 t3 M
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
' W; S) N. Y) u7 I0 R2 Q
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
: I( I" F9 S8 E/ b
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
7 C. \( h- q3 d% `9 Y8 S* D
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
9 Z2 z- b" ]( l, `8 I) w
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
. ?6 l) K( Q6 y# R2 @5 v5 R |
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
2 i& r: G; y a, a7 a
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
# P; }1 c8 Y: r6 ~ s
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
- Q3 U8 X- F+ P
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
" P/ N9 H- L: V$ U# k: s, c' j' Y* M
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
& G; X( t, T3 P& @) j) O
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
8 S; @' v3 j8 s8 A1 Q( ^7 Q
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
( C& H i; I( O, {4 s
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
( m/ q' y# {: n
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
% w# {. V3 R6 C+ ~! }, s5 I9 g
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
, } g9 ?' \( j; h. p. m
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
/ M2 c- b; C2 x+ ~0 {$ B
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
7 K' @: n+ I M5 E
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
$ v* E3 i$ J3 |. v9 Y' K& ?. J$ P
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
+ V5 D+ _3 y( X
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
7 m3 u+ x. ~+ W! c
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
6 y1 }: I$ C1 k A& V* I
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
9 `' w# ]# Y s
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
