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

释永思

最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0
% M% I0 ]2 p4 K8 s7 H7 l, {
                                作者：李均宇（李恒星）  2015.09.07
9 N% @  i7 e+ i8 V7 b9 E: f
8 @9 T5 @9 C2 X* j! M/ q   我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的：
( u% V7 [5 k, W- U( v/ @. @# L$ _8 T假设顶点数为N，
    N=4，5，6时，具体的弗法正确性，我就不想验证了。
假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？
" V# I7 A$ Q" h, a( }# t* M    先研究下N=n弗法正确时的特性。
N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N<n时，也就是最外层循环，每到一个值K时，此值K的弗法全是正确。
当N=n+1时，新加一点，称最后一点K。
' b& B8 X7 N" }4 s9 V, h6 \令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。
令最外层循环为k,中间层循环为j，最内层循环为i。
" C' E8 f# O# v: ?' }定理一：
   最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。
" T5 s# g3 }, v. d证明：
  假设点x经过最短路径D[i,j]，D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。
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].
9 O5 k$ P8 p, C# V所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。
" W7 [) O5 e" M3 E0 ?2 o1 {9 k定理二：
   最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。
4 j+ `& T9 m9 M4 H证明：
1 P4 L  f/ R% ~/ W   由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。
! u6 k" w- c' B+ x* [" s3 \+ c
定理四：
5 ^! U5 d1 h5 o   最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。
  \5 j" Q) K. y+ |证明：
. h3 X; C: \0 E4 U' N   k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。
此为max(i,j)<n之弗法，弗法已假设N<=n时全成立，现在求证N=n+1时情况。
7 L0 l5 R+ e; u! O# R: Z) I可知i,j必连通,即D[i,j]必非无穷大。
D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。
即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。
; C8 L9 y* f  i" j  r8 `/ {  J定理五：
   与k相连已经全是最短路。
8 z6 X7 N9 a$ ^, T- v证明：
) r$ s6 v- B) i4 e/ s   因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。

  `2 L' e! c) h. g/ v所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。
3 m$ {( m; E4 [3 F3 o4 p. z所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。
则N=n+1时，全部三重循环后，全部仍是最短路。
! j4 Q1 Z( F( U% _/ V3 U由数学归纳法知，三重循环的弗洛伊德算法是正确的。
2 _: M' l- L1 A) S///////////////////////////////////////////////////////////////////////////////////////
$ L: m0 Q! x  C; D, z. z0 X关于弗洛伊德算法的新证明：2015.09.23

5 \$ n6 B1 _( l' D7 Q  {4 I- ~* ~经过弗法的三重循环后，任意两点之间的距离已是最短路。
$ c7 f( \7 N2 C  _! p, N& r仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。
' n7 P" P! X+ N+ T/ ]) Q设k = n+1是最后一点。
如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。
# e% m( x$ c7 t1 Q3 p) i% V$ J% u如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。
5 p. _3 e' g% T$ G& k% v: c起点是a点,终点是b点,与k点直接相连的是c点,d点 。
当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。
k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。
例如k点连通cd，c点连通ad,d点连通ab。
又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。
* K" p; P4 }6 j7 V$ d所以命题得证。


) U/ h8 R: L5 P* b2 x; N( t
: G/ l! l6 T* f9 t6 ?
+ J& _6 L2 Y* T* A
3 a# U8 K% s2 X2 `7 k& F: x
% J: a# E; A4 H1 c: p



- @# ^8 c/ J# W6 f/ T, B



, W% d5 J0 c$ b1 T
1 ?) o  X+ h% e, C5 g

3 ^8 n' h, j" }" `

8 N" |; z; b% u2 W& i' G
: [4 e6 }' d  P7 A
! f* b) g9 h) j% k4 U: E

我的头大啊

顶·~~~~~~~~~~~~~~~
" R* `" V2 L6 I

风靡全球

加油
7 [( V1 N9 `; K8 _% {) N; i

风靡全球

加油
9 U# z8 y+ s2 S0 w# g0 [% Q

风靡全球

. _) p' g9 i3 P3 P8 n/ {+ v

风靡全球

加油

风靡全球

加油
: s$ `7 h5 `& y. f& u

风靡全球

加油努力
  h$ h( K% T& ~

风靡全球

加油  一定要努力哦
5 M# m* _( V! ?8 f' Y+ c# A# [

风靡全球

加油  一定要努力哦
2 H8 C8 ?3 p5 u# `