数学建模社区-数学中国
标题:
关于弗洛伊德算法的严格数学证明（草稿3）
[打印本页]
作者:
释永思
时间:
2016-4-22 17:08
标题:
关于弗洛伊德算法的严格数学证明（草稿3）
关于弗洛伊德算法的严格数学证明（草稿3）：
$ ]5 c# O; V$ W: N
2016.04.22
2 N }8 L3 h6 N6 C ^
; W) ?5 S ^ S9 s7 i+ d! W
经过弗洛伊德算法的三重循环后，任意两点之间的距离已是最短路。
$ Q6 p' M% m. ^
仍用数学归纳法，假设N <= n时，弗洛伊德算法是正确的，要证明，N = n+1时，弗洛伊德算法仍是成立的。
8 L" C/ D7 v# g o; U3 `8 A
设k = n+1是最后一点。
) c# ] P) a3 G+ T& Z5 G
任意两点间的最短距，如果是不经过k点的，显然floyd算法成立。
3 N2 t9 }3 i5 K! b2 v( _
任意两点间AB的最短距，如果是经过k点的。
2 m" V; `4 c1 B# @0 ^2 b
设路径为p=A....k....B，如果路径p中所有的顶点数P<=N，那么，把K点加入原顶点集合，把无关的顶点去掉，这三重循环就是N<=n的情形，所以弗洛伊德算法仍是成立的。
4 `; i$ F. q% Q4 b* W2 v$ J# C
如果路径p中所有的顶点数P=N+1，那么这是一条直线来的，没有任何分支的。要证弗洛伊德算法成立，可能不难了。每处理一个顶点中间点，必是连接一个线段，所以弗洛伊德算法得证。
2 t! E8 d1 q E+ X* b1 Z
所以弗洛伊德算法成立。
! ` K$ b1 ^- K F8 [6 @
) K1 Y8 m! _0 O/ T/ k0 M) N
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5