数学建模社区-数学中国
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
[打印本页]
作者:
释永思
时间:
2015-9-7 11:12
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
本帖最后由 释永思 于 2015-9-23 16:16 编辑
/ Y/ B( j! o' J- x' i2 b
& f$ G2 b3 H% ], b8 t8 x( A1 E
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
+ Z3 h* a4 f, E6 n& @7 Y1 H+ z- z. B5 g
% n9 j; }! S0 y/ U
作者：李均宇（李恒星） 2015.09.07
+ S5 r% l Q/ m/ v9 a' [
$ T7 ]9 x, b) P) _; N
我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
4 f6 L& O6 D+ v! b/ t+ ~
假设顶点数为N，
# n2 H$ v- b- M
N=4，5，6时，具体的弗法正确性，我就不想验证了。
+ [1 H. m; U# [# ?
假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
- I. G, P+ z& t C( W G
先研究下N=n弗法正确时的特性。
4 ?1 @$ l& `' t% f. R
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
: Y8 V; x, [7 J: d: s
当N=n+1时，新加一点，称最后一点K。
. ~0 W. _- X' @+ j" {
令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
& L/ J9 ?, E7 U
令最外层循环为k,中间层循环为j，最内层循环为i。
5 A0 Y9 ?: F- N8 G
定理一：
) W' t" `) ~- C* L. w* D5 _
最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
9 {) P! J. q0 J( o' Q5 {0 r
证明：
' Z+ H6 y6 E+ Z5 u# R! a; |( C' u
假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
) l1 `& w8 d! O2 B
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].
! |3 k4 z# m. ?
所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
# d! ?, D4 |( s
定理二：
4 k) i. F+ W1 Y, ^+ F
最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
' n8 B6 l" d& I" ~3 `9 f
证明：
/ W2 \" p: P$ U* i
由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
% K" g' f) ?9 @
. Z; {0 G! A( M" {0 N% v
定理四：
. _- Z- _" E4 a3 y( H0 U
最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
2 ^( n4 l: o$ ]5 R3 Q* c4 n
证明：
6 [4 B4 v; h7 w' x1 A& a
k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
) F) U9 a$ o- |) n: C+ a
此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
. ]7 B# _3 z+ G5 y
可知i,j必连通,即D[i,j]必非无穷大。
% X8 J! N! q9 E6 L Z1 J8 @
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
* [7 S! T% Z7 n/ p0 g6 X) F9 G
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
+ [" O; v3 t4 B
定理五：
6 H1 a) L2 I. ^/ t
与k相连已经全是最短路。
! _. ~) j' ^7 t& d5 Z# J
证明：
# ~, T4 |8 P$ i* ?, m) h
因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。
6 j& _0 `$ _8 ~7 U% t; m0 R
; c0 ]0 x( Q, V0 B3 B2 P# {
所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
: w6 r8 ]& [9 C; m
所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
8 s" p" j9 s% ]: J
则N=n+1时，全部三重循环后，全部仍是最短路。
6 O2 W3 L+ V$ Y4 l
由数学归纳法知，三重循环的弗洛伊德算法是正确的。
$ R& f* l0 L% H G$ s- ?+ A
///////////////////////////////////////////////////////////////////////////////////////
/ y: q- D; j7 M7 d/ _. h
关于弗洛伊德算法的新证明：2015.09.23
& ~: q1 c( E' H4 j K2 y) s+ {
# r- R" I# Q8 W
经过弗法的三重循环后，任意两点之间的距离已是最短路。
; y8 g$ d9 [. c [& w
仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
9 r! ], ~/ U" g S# J; v2 C+ T
设k = n+1是最后一点。
: G5 W4 z2 \) y" q/ n3 F
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
6 G8 `9 w' a; M
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
6 G1 q- F# _$ _1 a
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
- a! G! @0 j' o; S5 p' Q
当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
. N/ n9 N9 W! R
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
8 W, X0 ?, v& d3 |, ?* d
例如k点连通cd，c点连通ad,d点连通ab。
$ `; o0 O: ?# L
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
/ ]0 v3 K7 D$ {6 w* W; B0 t
所以命题得证。
% D9 M- O, H0 ^, A8 \; M
; w- H4 ?6 p- B9 a) D# V9 w8 n
) L2 Y" j, h1 {6 S: P
$ P" i% l% ?* _# j5 {" P
0 i, c5 L. x2 Y- V9 t1 p% Y
- u9 _! C6 V+ i0 N+ {+ D. f
f/ J: T+ Z, K$ b* h2 v8 @3 u6 m
5 F2 I! y: E% d
2 M; Q7 T1 }3 _* O
, m2 D1 ?' _% L2 I( w. ?
% @: }- s R: v; C) Y/ K
/ f% x8 O( ?" Y% k$ s& J. H
4 s, |1 e8 f7 @4 T; H$ U
; r: Y% M0 b8 V* H8 r
. D6 V8 }( U5 Q. n* |5 f
0 [4 k" w" z/ R7 m, x# Q! h
* p0 p! G D% H2 L* i _
. I( a9 ]+ d0 F% C
. I J+ u6 J7 N/ z8 [
# M) w8 K! V0 f; E) e( f: E5 v
' M# t3 p4 ~( M/ Y4 D
& Z- B, ^6 q2 b- Z
. L. k& V$ w1 o* i! }0 h
作者:
我的头大啊
时间:
2015-9-7 13:04
顶·~~~~~~~~~~~~~~~
2 {: ]6 U1 |: g( K$ \2 Z
作者:
风靡全球
时间:
2015-9-10 17:52
加油
4 q4 t$ q7 _' Z' y% W0 A
作者:
风靡全球
时间:
2015-9-10 17:52
加油
) k/ L0 _, E7 W' X* b
作者:
风靡全球
时间:
2015-9-10 17:52
, d! g2 Z7 X3 J
作者:
风靡全球
时间:
2015-9-10 17:52
加油
* K9 {* U2 m, h5 G. j0 z! o2 e# T5 H
作者:
风靡全球
时间:
2015-9-10 17:52
加油
; z& ~7 Z' T0 Z3 {' S
作者:
风靡全球
时间:
2015-9-15 16:59
加油努力
: ?3 k6 D2 b* |! T4 I& b
作者:
风靡全球
时间:
2015-9-16 17:58
加油 一定要努力哦
( q( A, o7 U7 A0 k
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
0 Z. X6 o! q% X: M; G9 M. D
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
. [4 e( I4 J( h/ K, w C# w' @
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
: J2 ?- N( d1 P5 \, L* A( b }
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
# F) e4 a2 Z4 @) c8 h. l
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
; b: k, n1 D: z: [8 @1 Y
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
7 k9 g6 U' Q! }: @
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
; i) \ E- I6 a0 k. Q8 s7 A
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
- o' p; J( p5 c, l9 w
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
% U' t j) g8 h5 h
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
" u# @3 y* L) `- ?! K9 S7 y
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
4 P5 P% `/ w$ K
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
% x+ ~* L! d$ N' s$ X& @
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
: P4 z z' F) S6 _. x! ]
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
2 K4 ?. `& g% U. D( N) v
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
% U/ x, u# N0 Z; U( t1 _
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
$ \8 F/ o7 J1 N8 x- j
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
) Y1 K) h2 J! c$ B! a6 I% M
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
. S$ [. P- C7 m2 Y
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
$ J- A1 u, I! D, P' }/ K* q' y- a" I
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
4 g6 D+ I0 I3 a `( S- C7 P1 U
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
1 z, Y3 p s: P" j9 H
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
$ c* w( i b5 ]. Z0 L5 O
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
4 S* q6 {: N0 Q; z
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
, r/ J5 W4 W5 U
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
