数学建模社区-数学中国
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
[打印本页]
作者:
释永思
时间:
2015-9-7 11:12
标题:
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
本帖最后由 释永思 于 2015-9-23 16:16 编辑
; I4 I: \2 w" @5 H; L, {
4 E, y/ i# X7 W1 ?6 o
最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
5 S S G# C. V$ W& b* L! y3 e' [
% K; m f, J/ N0 h( B
作者：李均宇（李恒星） 2015.09.07
" R9 s2 u7 Z+ v* T7 i6 W
: H4 A+ m$ o9 e4 f
我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
; _& ?5 c- q. i. r2 H" k( k% b
假设顶点数为N，
# V% E% L! @8 e
N=4，5，6时，具体的弗法正确性，我就不想验证了。
6 N5 s$ W" I4 P8 p
假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
" k, t4 {5 t5 q8 \$ C2 L
先研究下N=n弗法正确时的特性。
& c+ I; {% | I" B/ }7 ?; s5 x
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
2 l; y# ]. h6 s/ s3 b' T
当N=n+1时，新加一点，称最后一点K。
$ W4 ^8 S# h. ^1 S+ L. V) Y
令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
9 F9 v6 I; C$ ^1 m
令最外层循环为k,中间层循环为j，最内层循环为i。
7 @3 h, f, C* m, L
定理一：
/ B$ j4 Q6 f: e7 c& o7 \# P
最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
3 B1 ~ D p; w
证明：
! }# n2 \, s& ~% m9 p, Q3 J$ W
假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
$ K! J; Z+ O: W: h
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 Z" k( V; F! e" W
所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
_- e; d' D/ ?) f j9 W W
定理二：
5 D4 m9 {7 [ Q- `, F3 g
最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
9 Q" @4 N9 {; \. J
证明：
8 |; x) K' s5 N& Y$ |+ _
由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
. T* [9 E# E2 T& Q+ k$ G- f
! @6 v6 J( X" B: R8 ^6 X
定理四：
; u1 b0 [/ \0 F1 U* O- m# v3 P c" U
最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
: g: [7 A8 J5 ^& Z/ {& |
证明：
8 x/ ?# k! V) T0 ?1 d' ?
k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
- X" ?5 J! g* H- p* L7 I7 P
此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
5 O* ?/ `; b4 @7 z4 H5 |7 ^
可知i,j必连通,即D[i,j]必非无穷大。
6 o. E0 E6 Q, J3 H" r: }
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
F) [# R- A/ d3 R
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
; k& y& H( a2 G7 \
定理五：
) S3 I# T4 x0 x) ?( m
与k相连已经全是最短路。
' ?2 ?' d7 A) V0 h1 D3 S& a
证明：
8 R/ J8 P. b% k
因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。
6 v7 }" d/ G* r) n2 \" S) `
% J+ W7 z' L: B6 X
所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
# e z k0 d# n) q
所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
6 e6 a% i: C% U, G
则N=n+1时，全部三重循环后，全部仍是最短路。
8 c1 ~) t- d! M/ u5 u6 v
由数学归纳法知，三重循环的弗洛伊德算法是正确的。
7 V! [. O. \! _- ~' k
///////////////////////////////////////////////////////////////////////////////////////
; b6 }2 k x8 A6 Q: ~9 h
关于弗洛伊德算法的新证明：2015.09.23
1 _ Z0 g& I( e0 | e. @* I
: _+ l- M' w' k) l
经过弗法的三重循环后，任意两点之间的距离已是最短路。
/ h1 T! b1 Q$ U
仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
5 t3 F0 Z1 C% b% ?6 |+ i3 W
设k = n+1是最后一点。
3 k Y" Y5 c+ q! F! F# [0 ~
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
' a6 J3 y* b. h" r* t" W
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
M; x) G! W# F# M8 e# p
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
% D9 R/ W# u/ s; ?. s/ o+ J
当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
/ O$ O/ x: }. W! T1 V
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
' N$ g B3 v& T9 `+ L
例如k点连通cd，c点连通ad,d点连通ab。
6 r3 A& x- J- h6 r' ]. z
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
* i9 ^* }: c+ Q4 k* g
所以命题得证。
, _$ P& K" ?; m4 K8 ?
: f- O$ x3 M) [# J w7 j0 h
! a: M+ P8 L7 V/ m5 f7 |$ s
( k9 `5 F6 u4 X! a y
; S' e# f( E9 P; P1 R' v
T' e! K. Z' m8 o) |* k$ {
4 s: }) i% d" T. o' @
$ ~2 Z2 _0 p! K) K& F
* `* X. R5 b' O4 w/ q2 q8 p
7 S9 ` s- X5 w$ J
" ?) y$ ~% H, o1 q4 ]( S- a7 S
' ?& Q" U7 f5 l8 z) \
" N! I$ v! f O. ~- {% U t
! A; l) k+ k9 R+ i
+ D* T( Z2 }+ \/ j/ ?- w
: I7 }* z) B4 O
# V, Z! `6 B' j. F* J/ k5 P% ^
) U m) u- Z/ ?7 ?# g& p% s" S
6 \1 e% N& v, _2 |( M- ?% i3 h3 S
. J/ H' Z7 h" m4 ^8 S
w: N; ]% w' N0 o$ z
9 n8 o. G3 E1 T! N9 ^4 @: u
* d' J7 r b- M, q) E( g. z
作者:
我的头大啊
时间:
2015-9-7 13:04
顶·~~~~~~~~~~~~~~~
# G }! R8 w! X# x! |" H' J' B6 E
作者:
风靡全球
时间:
2015-9-10 17:52
加油
+ Z* D% @, [ M& |
作者:
风靡全球
时间:
2015-9-10 17:52
加油
* [) b9 n7 P# m6 i; C+ d0 R7 L
作者:
风靡全球
时间:
2015-9-10 17:52
% ~3 B% b& V2 K
作者:
风靡全球
时间:
2015-9-10 17:52
加油
2 b, J7 d5 e3 k$ j& ~
作者:
风靡全球
时间:
2015-9-10 17:52
加油
8 c, O7 i5 H: R3 |0 |
作者:
风靡全球
时间:
2015-9-15 16:59
加油努力
$ ~% I( Z) }* |7 @. V
作者:
风靡全球
时间:
2015-9-16 17:58
加油 一定要努力哦
: f/ \, ~6 W, u1 k
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
?% Z0 l9 s9 X
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
+ h {& e; ]- ^
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
/ }( N, o: v5 a: {
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
, o' L4 i( D% D+ {
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
% S5 `" {. i# ^7 x T2 S# w
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
. Z$ p3 r. T% c
作者:
风靡全球
时间:
2015-9-16 17:59
加油 一定要努力哦
- a( o1 k( Y6 u
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
W/ q q$ r3 ?6 ~( p9 |# ~8 j) N
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
; \3 V- [, r5 m5 j
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
% b* ^5 h$ M9 w5 s9 k( ]) F
作者:
风靡全球
时间:
2015-9-17 17:47
加油哦 努力哦
4 t- n7 \& j) x* G. w
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
# N+ w0 Y# k. }7 X3 J
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
9 r: e- b4 j5 v( x- u
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
1 ~* @2 r) v2 y
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
+ o5 l3 a2 s4 Y |: q; }
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
; s( x, S5 }- h
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
7 U9 Z" E2 x+ R5 F2 ^
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
! W& e( _, i. B6 ~1 p
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
5 L* D; b9 q' Q+ j9 R# e
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
5 S6 z: n& @7 {! r9 s
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
4 Z( G, W( d ~6 G5 y; v) k
作者:
风靡全球
时间:
2015-9-17 17:48
加油哦 努力哦
! ?! R! P! y, a) s, Q
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
$ C3 G# x& C; m5 s7 A/ ]
作者:
风靡全球
时间:
2015-9-17 17:49
加油哦 努力哦
; N+ x6 U' v- ]" J4 w ^
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
% ~3 B% b& V2 K