内容发布更新时间 : 2024/6/26 19:10:07星期一 下面是文章的全部内容请认真阅读。

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

我二十年前已了解迪杰斯特拉算法，最近忽有兴趣开发了一款最短路径算法小软件EXE，了却二十年前的心愿。余庆未了，网上了解了还有多种方法，如A-Star,johnson,bellman,SPFA等算法，其中最感兴趣的是弗洛伊德算法。百度了，看了很多源码，大同小异。但对弗洛伊德算法原理，网上讲的，我看后也觉似懂非懂。利用抗战70周年纪念日放假期间，我闭关冥想，想到了N步的方法，但冥想出来的源码，总比网上讲的多一层循环。于是继续冥想，想到了要用数学归纳法来证明弗洛伊德算法。百度下，好似网上暂没这方面资料，于是共享出来，与诸君分享，不知对错也，网上讲到的什么迭代法，总是不太对似的，弗法可能并没有这么简单的： 假设顶点数为N，

N=4，5，6时，具体的弗法正确性，我就不想验证了。

假设N<=n时，弗法是正确的，如何证明N=n+1时，弗法仍是正确的？ 先研究下N=n弗法正确时的特性。

N=n时，所有的n个顶点两两组合的边D[i,j]，不论虚边实边（直接的称实边，要通过其他顶点的叫虚边，我如此定义先），全部有值，且为最小值最短路径。N

当N=n+1时，新加一点，称最后一点K。

令最后一点K总在循环中排在最后一位，三重循环中都是排在最后一位。 令最外层循环为k,中间层循环为j，最内层循环为i。 定理一：

最后一点k若改变i与j之距D[i,j]，则所有经过i与j之最短路必同步更新且不分先后。 证明：

假设点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].

所以D[i,x]>=D[i,k]+D[k,x]，所以x点必被更新，也就是执行松驰操作。 定理二：

最后一点k若改变i与j之距D[i,j]，则经过i与j之最短路必不经过最后一点k。 证明：

由定理一知，如果经过最后一点k，则D[i,k]本身要变，但正是用D[i,k]来执行松驰操作的，所以矛盾。

定理四：

最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大，即必已连接(不论虚边实边)。 证明：

k为最内层循环点最后一位。取i,j最小者位于中间层循环，最大者位于最外层循环。

此为max(i,j)<=n时全成立，现在求证N=n+1时情况。 可知i,j必连通,即D[i,j]必非无穷大。 D[i,k],D[j,k]两个不可能都是无穷大，这可以取min(i,j)来递归而知,min迭代到一条实边则可止，或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。

即知D[i,k],D[j,k]必有一个是连通的，D[i,j]也是连通的，从而三点必全连通，必非无穷大。 定理五：

与k相连已经全是最短路。 证明：

因为与最后一点k相连的，全部没有变动，全部已非无穷大，所以经过k点的必是最短路。

所以新增一点k，由定理五知，当最外层循环到最后一位k时，所有经过k点的已是最短路。

所有对原来N=n时的弗法最短路的调整松弛操作，全能同步更新经过相关点的最短路，也就是原来的n个点的弗法，后来仍是最短路。 则N=n+1时，全部三重循环后，全部仍是最短路。 由数学归纳法知，三重循环的弗洛伊德算法是正确的。