数学建模社区-数学中国
标题:
关于弗洛伊德算法的严格数学证明（草稿3）
[打印本页]
作者:
释永思
时间:
2016-4-22 17:08
标题:
关于弗洛伊德算法的严格数学证明（草稿3）
关于弗洛伊德算法的严格数学证明（草稿3）：
$ F0 s; \; q& Y7 f2 Z9 V9 |3 i( O/ \
2016.04.22
- [% T- u2 x( x, U
$ P: ]. z$ Z3 S2 B2 T+ D
经过弗洛伊德算法的三重循环后，任意两点之间的距离已是最短路。
3 H5 S& r( r* F
仍用数学归纳法，假设N <= n时，弗洛伊德算法是正确的，要证明，N = n+1时，弗洛伊德算法仍是成立的。
+ n. @$ E( q8 K$ C
设k = n+1是最后一点。
7 ^7 L) p9 g, i
任意两点间的最短距，如果是不经过k点的，显然floyd算法成立。
; g) E- _3 u3 r6 R
任意两点间AB的最短距，如果是经过k点的。
! N; o" z$ Y$ x1 u/ a9 r: B8 H; Y K
设路径为p=A....k....B，如果路径p中所有的顶点数P<=N，那么，把K点加入原顶点集合，把无关的顶点去掉，这三重循环就是N<=n的情形，所以弗洛伊德算法仍是成立的。
/ ~; T$ V! t& d. Q- K6 y
如果路径p中所有的顶点数P=N+1，那么这是一条直线来的，没有任何分支的。要证弗洛伊德算法成立，可能不难了。每处理一个顶点中间点，必是连接一个线段，所以弗洛伊德算法得证。
! v# `/ j! X0 F0 q! W+ z5 w k
所以弗洛伊德算法成立。
1 `# f8 t4 o# Q1 S' C! `0 C
0 u1 J* D/ _0 b# i
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5