在线时间 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
自我介绍 软件开发工程师
=========================================
4 }: k8 w" y$ y: ~ 最短路径中的Floyd算法(弗洛伊德算法)的较为严格的冥想证明过程:, C, ?: {* c) j
仍用数学归纳法,- r5 z l, B! k, t: d) y
假设N<=n时,弗法正确。具体值我就不验证了。5 v2 Q" s3 u& s
当N=n+1时,假设最新一点最后一点为K,此时K=n+1,) |: ]! b; O z K1 ^1 \" H8 l
三重循环中,我们都把K排在循环中的最后一位。' m+ f" r: L( i3 `$ W' Y( `7 n
现在我们要证明的是,加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。
8 z6 S& G* k; H, e7 s& b, _$ M 如果原来的n点的某两点之间最短距是与K点无关的,显然经过三重循环后,就是最短距了。3 B1 ? m4 H# v# {
如果原来的n点的某两点之间最短距是经过K点的,假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距。& B0 @1 F0 J2 T; O0 P8 ~
那么由弗法知,P1,P2,P3,,,Pk-1与PK+1,,,,Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边,不是虚边。 q5 R# v; ^. s& ~6 C
经过最外层最后一次循环的松驰操作,必能连通P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
; {; I+ k2 g F5 J' }7 q 所以得证:加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。 z# h4 b) _, e. Z
由于对称性,将K点置入内部,把P1点放到最后一点,原来的循环结果不会变的,) o% a& ~) b: E! y+ C
所以三重循环后,K点与原来的点(除P1外)的最短距,就可以求出来了。' {* @9 j# ?3 v
由于对称性,将K点置入内部,把P2点放到最后一点,原来的循环结果不会变的,
9 Y* `3 o9 K2 g+ O5 w1 b$ R9 W: K6 _2 M 所以三重循环后,K点与原来的点(除P2外,但P1不除外)的最短距,就可以求出来了。! K' T/ o$ w1 T6 g* J, d0 C
所以K点与原来的n个点的最短距,也就已经求出来的了,仍是原来的三重循环也。
$ }& c% t1 Z& M; K0 B! m 这样,弗法就可以较为严格的证明了。
, {, B* g6 n" z9 O3 y, V# a =========================================' u9 f1 G+ P0 b& ~
为何假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距???
* o- e/ o$ E+ X2 D S# \ 如果是虚边最短距,也可以转化成实边最短距,然后结果一样的。) y+ w( v v0 y. d: f4 F! g; S: D
=========================================
6 f: s9 l2 o: r/ K# q! K
" b& d o1 [! Q 2 q `) _' a4 \9 [( Y
zan