最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0

释永思

4 m" s9 k: r% O3 _0 j, ^7 q
$ H; W8 s0 q, W6 L最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0

' e3 U/ a5 l. F' Q" f( b                                作者：李均宇（李恒星）  2015.09.07

   我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
& M2 E3 v& I- A9 N! ?1 j8 F: E+ J假设顶点数为N，
    N=4，5，6时，具体的弗法正确性，我就不想验证了。
+ h* F1 K4 D2 a4 t& [) q. i假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
! A( x; J2 X' G+ Q' F; S  _6 ?    先研究下N=n弗法正确时的特性。
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
2 K7 z5 ?' j1 m$ B% `* D当N=n+1时，新加一点，称最后一点K。
令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
2 @$ k  G9 T+ w0 Z令最外层循环为k,中间层循环为j，最内层循环为i。
6 M' F- Y9 j- P- a4 a+ X$ i定理一：
   最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
证明：
& h. k+ y, a- F  假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
2 F9 i- {! d, K6 v' iD[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].
: s* n5 W% E1 X/ B所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
定理二：
, k" X+ K( q; ]" |/ e   最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
9 V) R* [' }4 o) \3 U证明：
   由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
. P4 n8 B* {$ K# w7 E/ H
定理四：
   最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
; }: Z) a3 ^9 z7 i证明：
+ a1 F# E8 _, o9 {$ Q: M   k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
- ?  L& c4 ]) T0 E% L* ^9 j; v此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
. X  Y4 Y4 `0 Q可知i,j必连通,即D[i,j]必非无穷大。
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
# a: D: u7 Y9 B% e: i! v( ~+ A即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
定理五：
6 m) c' Z9 F( Y0 Q! C* ~   与k相连已经全是最短路。
证明：
* @& {+ w8 m  M( z* L% Y. a  H! L   因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。

% _- b4 r7 C) R) H- \所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
, }' |, {# ?2 `1 D7 z则N=n+1时，全部三重循环后，全部仍是最短路。
由数学归纳法知，三重循环的弗洛伊德算法是正确的。
///////////////////////////////////////////////////////////////////////////////////////
: Y5 [3 l' v. Z关于弗洛伊德算法的新证明：2015.09.23
% K: r% g2 z9 p, J# d
' I& u8 w9 s3 G4 `经过弗法的三重循环后，任意两点之间的距离已是最短路。
; B8 D5 X' W- P1 W* J( h6 O! A仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
: F+ F; w8 Z' g' t7 \6 r$ E9 P设k = n+1是最后一点。
; x  l& k/ G8 V+ r9 [  M5 Y$ d4 P如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
4 F7 ^( M/ E2 S+ M7 z2 T如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
/ \& S7 c9 B' \# o. D当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
# W2 v/ w4 k4 y7 r例如k点连通cd，c点连通ad,d点连通ab。
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
  ~  S2 `! Q& z* q2 S$ N" `; t/ L所以命题得证。

3 n0 }/ {8 V! M# c$ z
+ v8 z. K  h% z) o7 p6 L' D
: w% r0 X# C0 }+ h


) H0 B: L1 _5 E' o0 B

9 l9 b' l1 }3 N* |4 ?# w
+ s5 B. O3 `' i& U

* t( a( z  Y' W+ f+ J
4 }8 V  D) s8 d* v


# K+ b: k$ l# Y7 x) l' D% Q
5 y# J6 v' ^) T5 N8 M* \; ^& W* D0 [
# Z* e' c" y$ T! X1 E
- s* k# r' t  @! \9 h2 W
, t5 ^$ R1 q: n0 ]% ]7 J3 ^


: y, g& x) R6 F

风靡全球

加油哦   努力哦
0 U9 ]' u3 \9 w6 y( q' H2 n

风靡全球

加油哦   努力哦

风靡全球

加油哦   努力哦

风靡全球

加油哦   努力哦
) l+ B, m6 h. Z$ h8 Z" A$ K

风靡全球

加油哦   努力哦

风靡全球

加油哦   努力哦

风靡全球

加油哦   努力哦

风靡全球

加油哦   努力哦
. G1 }9 e2 b% E! }3 a& N, `

风靡全球

加油哦   努力哦
1 X/ F* Q: L7 D' S9 F