- 在线时间
- 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
- 自我介绍
- 软件开发工程师
 |
=========================================
8 d1 U6 G8 L$ f w最短路径中的Floyd算法(弗洛伊德算法)的较为严格的冥想证明过程:
& p( S a* R6 H仍用数学归纳法,% P% P4 o' \$ H9 v# U+ a- U, K
假设N<=n时,弗法正确。具体值我就不验证了。
- A1 Z, } l2 `$ m当N=n+1时,假设最新一点最后一点为K,此时K=n+1,
0 o+ ?: f7 A5 }9 ]三重循环中,我们都把K排在循环中的最后一位。
% Z; R* r+ s) t% t现在我们要证明的是,加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。
* B8 m. |9 W, n* O7 H% Y6 {如果原来的n点的某两点之间最短距是与K点无关的,显然经过三重循环后,就是最短距了。1 @, z+ z( L% g
如果原来的n点的某两点之间最短距是经过K点的,假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距。
- \) Z; L* @3 |! l4 W那么由弗法知,P1,P2,P3,,,Pk-1与PK+1,,,,Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边,不是虚边。8 b$ l3 x K8 B& Z1 i* q. i/ v1 B
经过最外层最后一次循环的松驰操作,必能连通P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。. }/ f9 _5 B% Y2 x, r& y3 d! B0 F
所以得证:加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。1 S4 V" g0 c" @6 T3 m0 T
由于对称性,将K点置入内部,把P1点放到最后一点,原来的循环结果不会变的,
; Z6 }/ B0 N3 D) L6 C+ h8 C所以三重循环后,K点与原来的点(除P1外)的最短距,就可以求出来了。" d$ P7 T% p1 q
由于对称性,将K点置入内部,把P2点放到最后一点,原来的循环结果不会变的,& H, w4 k: c/ \- e i9 V
所以三重循环后,K点与原来的点(除P2外,但P1不除外)的最短距,就可以求出来了。+ V8 g! a3 ]/ y( ~0 Q
所以K点与原来的n个点的最短距,也就已经求出来的了,仍是原来的三重循环也。
* C' i0 @' j4 y' Z& Y这样,弗法就可以较为严格的证明了。- x& L* U$ a6 T+ [2 P0 ^; x
=========================================
+ _! i# [9 `- z5 r* F; I3 b为何假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距???
( p) a6 e; w3 N& ]+ |% L如果是虚边最短距,也可以转化成实边最短距,然后结果一样的。
) O/ ]- I7 Q9 C, X! V+ [=========================================1 x( i# N* d4 f1 I7 x+ L0 i
0 f4 o% u7 O B, Q# |8 q
P$ C1 g/ L9 L+ e |
zan
|