关于弗洛伊德算法的严格数学证明（草稿3）

释永思

关于弗洛伊德算法的严格数学证明（草稿3）：
2 h) c% E9 K+ e  a                   2016.04.22
+ H. l, X4 R0 H4 Y
3 N0 z* n! f0 N$ z. w经过弗洛伊德算法的三重循环后，任意两点之间的距离已是最短路。
+ ^2 h; a5 S- x仍用数学归纳法，假设N <= n时，弗洛伊德算法是正确的，要证明，N = n+1时，弗洛伊德算法仍是成立的。
* e1 z2 }) t6 C9 \; m# t8 R设k = n+1是最后一点。
" ?3 X* q7 c" b: t; n8 i7 ]8 w任意两点间的最短距，如果是不经过k点的，显然floyd算法成立。
8 `4 g. e" R9 ^  W# {- m0 o) v任意两点间AB的最短距，如果是经过k点的。
设路径为p=A....k....B，如果路径p中所有的顶点数P<=N，那么，把K点加入原顶点集合，把无关的顶点去掉，这三重循环就是N<=n的情形，所以弗洛伊德算法仍是成立的。
如果路径p中所有的顶点数P=N+1，那么这是一条直线来的，没有任何分支的。要证弗洛伊德算法成立，可能不难了。每处理一个顶点中间点，必是连接一个线段，所以弗洛伊德算法得证。
) S/ G6 p- G% L5 y, ?' a所以弗洛伊德算法成立。
( V. p, y* K- N& A1 w# d. K
; F$ G. \! V  v