数学建模社区-数学中国

标题: 关于弗洛伊德算法的严格数学证明（草稿3） [打印本页]

---

作者: 释永思    时间: 2016-4-22 17:08
标题: 关于弗洛伊德算法的严格数学证明（草稿3）
关于弗洛伊德算法的严格数学证明（草稿3）：
                   2016.04.22

经过弗洛伊德算法的三重循环后，任意两点之间的距离已是最短路。
3 b* r& J7 X$ y" `5 U' X; W4 ~仍用数学归纳法，假设N <= n时，弗洛伊德算法是正确的，要证明，N = n+1时，弗洛伊德算法仍是成立的。
设k = n+1是最后一点。
. S+ {: o+ z9 C! W1 x任意两点间的最短距，如果是不经过k点的，显然floyd算法成立。
, l7 X, q2 [$ T* J- O任意两点间AB的最短距，如果是经过k点的。
: B4 F; Y7 o# s& H+ o设路径为p=A....k....B，如果路径p中所有的顶点数P<=N，那么，把K点加入原顶点集合，把无关的顶点去掉，这三重循环就是N<=n的情形，所以弗洛伊德算法仍是成立的。
# H  j7 M! |* X% L如果路径p中所有的顶点数P=N+1，那么这是一条直线来的，没有任何分支的。要证弗洛伊德算法成立，可能不难了。每处理一个顶点中间点，必是连接一个线段，所以弗洛伊德算法得证。
所以弗洛伊德算法成立。
9 J- `9 w  i; q; {
+ }; G9 z' U- G5 J( D) G1 t3 D

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5