- 在线时间
- 138 小时
- 最后登录
- 2018-11-1
- 注册时间
- 2015-8-26
- 听众数
- 13
- 收听数
- 0
- 能力
- 0 分
- 体力
- 366 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 146
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 70
- 主题
- 23
- 精华
- 0
- 分享
- 0
- 好友
- 17
升级   23% TA的每日心情 | 难过 2016-5-14 14:04 |
|---|
签到天数: 18 天 [LV.4]偶尔看看III
- 自我介绍
- 软件开发工程师
 |
关于弗洛伊德算法的严格数学证明(草稿3):
- s7 M* w1 W6 G 2016.04.22
* A& f. R& o0 u2 l* S$ }3 F$ b6 C/ |) J1 `! V
经过弗洛伊德算法的三重循环后,任意两点之间的距离已是最短路。
( `7 k( @! a5 N3 r仍用数学归纳法,假设N <= n时,弗洛伊德算法是正确的,要证明,N = n+1时,弗洛伊德算法仍是成立的。
% m* x# h9 [; B" P设k = n+1是最后一点。 / O: E" M2 t" r Z) J: d' b
任意两点间的最短距,如果是不经过k点的,显然floyd算法成立。
% U% {6 }7 E+ j3 U任意两点间AB的最短距,如果是经过k点的。: u8 j7 p U6 [$ ~! S# T. C6 z
设路径为p=A....k....B,如果路径p中所有的顶点数P<=N,那么,把K点加入原顶点集合,把无关的顶点去掉,这三重循环就是N<=n的情形,所以弗洛伊德算法仍是成立的。
) N* _, @ b4 G* {! U' L) O8 s如果路径p中所有的顶点数P=N+1,那么这是一条直线来的,没有任何分支的。要证弗洛伊德算法成立,可能不难了。每处理一个顶点中间点,必是连接一个线段,所以弗洛伊德算法得证。9 y2 B* ^& l- ]. N+ C
所以弗洛伊德算法成立。$ {% T; r* ] {5 e1 S' |
- @+ |1 m) R0 q; e) D X1 [
|
zan
|