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

释永思

+ e6 {6 e# ~* W7 a0 }
" d& X' N2 {+ O2 ?. F  X* [# G最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0

3 a$ w8 [3 O7 z/ M* q: w                                作者：李均宇（李恒星）  2015.09.07
" z6 q, a& A5 p) D1 I" i
. t$ U- E5 \. y$ o  b1 }% P   我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
假设顶点数为N，
: G, b0 Y& K' n4 G% J; u    N=4，5，6时，具体的弗法正确性，我就不想验证了。
$ u, {6 {7 d( n4 i2 g假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
/ H2 w$ ^7 u- |5 `- G) J" k    先研究下N=n弗法正确时的特性。
; j7 h# G: I2 T: ?: C' q5 ~) |: IN=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
* e! c2 v$ g9 P* i0 U* V当N=n+1时，新加一点，称最后一点K。
# v! }' ?9 _$ v9 `令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
令最外层循环为k,中间层循环为j，最内层循环为i。
定理一：
   最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
/ W8 L9 ?, Q# V% u: u( n( B4 Q9 V证明：
  假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
% X, N: n0 t5 I! i6 N1 Y' ]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].
所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
3 n( Z7 Z" H+ E5 L定理二：
( b2 Y  @; ~$ {6 o7 n6 [$ n   最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
- D% n& x" U! a证明：
- o% M, y- U( g" E7 E( }1 e7 \   由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。

定理四：
1 y. L+ m# o- e1 C% X4 b) ]   最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
  K0 s7 Z! V( y# G" i证明：
   k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
! S$ k1 E1 ~! E' ?' ]8 P7 c. v/ n此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
. A7 _( d9 x. ?可知i,j必连通,即D[i,j]必非无穷大。
; j/ _8 W# Y0 g8 CD[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
* \, f. i/ i4 e" O2 s9 ~5 k; H4 q定理五：
; y' m3 K9 y* |7 P: Z5 D$ V( u   与k相连已经全是最短路。
证明：
1 V! Y5 k$ H  u8 n   因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。
; c1 X5 V8 @, r) p
所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
& a; y# z( C) M所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
, ?) W, y2 s/ |0 ]2 U  h& Z则N=n+1时，全部三重循环后，全部仍是最短路。
) P) D( R* l/ ]- _由数学归纳法知，三重循环的弗洛伊德算法是正确的。
7 z$ A* S# V- H- ?2 Q. W" H///////////////////////////////////////////////////////////////////////////////////////
' p- p5 V: e* @  s' d关于弗洛伊德算法的新证明：2015.09.23
/ z' W2 H; s6 W8 g, ?
经过弗法的三重循环后，任意两点之间的距离已是最短路。
7 y+ `0 T# O$ H# ^/ u9 Z. G2 @' n仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
设k = n+1是最后一点。
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
起点是a点,终点是b点,与k点直接相连的是c点,d点 。
4 Q9 s* D, w. `: y/ A. W当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
1 A( g" [4 p0 w1 K& l- n9 u* O5 b例如k点连通cd，c点连通ad,d点连通ab。
  c+ x2 a$ R6 M+ [又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
所以命题得证。



! [# p& t# a1 ^; g+ P7 Y

; g. a0 p0 [3 U( c- S
' f; d# V1 T: X6 A' m% V% X

! T* o, s# Y7 w; h8 U
+ u3 X; U6 o5 M
3 k5 {8 |' h$ z" h: y' w
, }2 y/ n2 a! O+ [


& N0 `! E7 `# a4 g. W- ?3 Y

) d( S) K8 p8 S$ }0 j
+ z, h# W& e( t* o. F
2 [; j' D! Z- J: P+ ]( Q

7 M! a. F7 Z* V$ c* X' b1 i

我的头大啊

顶·~~~~~~~~~~~~~~~
2 W) A8 I2 ^1 r" h& d+ R; I

风靡全球

加油
! k! q, C7 p2 F0 s0 @

风靡全球

加油

风靡全球

% |1 h, c7 H3 J$ k' X

风靡全球

加油
* r$ A1 s% _- J. w* c; q

风靡全球

加油
4 a" R  `- _8 x: u

风靡全球

加油努力

风靡全球

加油  一定要努力哦
6 M; ~/ V4 ^! B# }9 u

风靡全球

加油  一定要努力哦
- U/ O: X8 F/ `; y+ W9 {