QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5643|回复: 12
打印 上一主题 下一主题

[问题求助] 最短路径中的Floyd算法(弗洛伊德算法)的较为严格的冥想证明过程

[复制链接]
字体大小: 正常 放大
释永思        

23

主题

13

听众

146

积分

升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    跳转到指定楼层
    1#
    发表于 2015-10-31 13:45 |只看该作者 |正序浏览
    |招呼Ta 关注Ta
    =========================================7 s7 e$ H2 W0 T' E5 F
    最短路径中的Floyd算法(弗洛伊德算法)的较为严格的冥想证明过程:
    ( w& w% X8 M/ I4 S: B仍用数学归纳法,& U; {9 U9 Z; w4 B
    假设N<=n时,弗法正确。具体值我就不验证了。. d  a$ O& C3 n; {, @
    当N=n+1时,假设最新一点最后一点为K,此时K=n+1,
    7 M& m" n, y8 U- L2 b9 ~4 X) B三重循环中,我们都把K排在循环中的最后一位。
    ) I9 q; D7 Y) m  q! s现在我们要证明的是,加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。4 K$ p4 L: h5 b' M- `6 \  P/ E
    如果原来的n点的某两点之间最短距是与K点无关的,显然经过三重循环后,就是最短距了。. _, {6 S1 w1 h" |: {
    如果原来的n点的某两点之间最短距是经过K点的,假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距。
    1 G& W  v+ j, |那么由弗法知,P1,P2,P3,,,Pk-1与PK+1,,,,Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边,不是虚边。/ O( q: s1 s& h  f# x% C
    经过最外层最后一次循环的松驰操作,必能连通P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。3 z; ~, d- S! x. p6 A, Q( D
    所以得证:加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。
    ( ~2 n* s9 d/ W' w  F由于对称性,将K点置入内部,把P1点放到最后一点,原来的循环结果不会变的,
    ! R) J/ U# K  o' V. t, m所以三重循环后,K点与原来的点(除P1外)的最短距,就可以求出来了。
    ; U/ A6 U7 G$ ?+ B/ {1 Z& i- c9 @由于对称性,将K点置入内部,把P2点放到最后一点,原来的循环结果不会变的,
    9 w% o2 f! R( s. m4 p' d0 w所以三重循环后,K点与原来的点(除P2外,但P1不除外)的最短距,就可以求出来了。7 k$ H: L& s; A9 A  w) ]5 o- q
    所以K点与原来的n个点的最短距,也就已经求出来的了,仍是原来的三重循环也。
    2 y3 s9 R/ m) B# v; O/ J- F这样,弗法就可以较为严格的证明了。
    4 Y: I, D' s* K0 w+ i/ K=========================================. o1 @$ l2 l! Y5 M/ {) n
    为何假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距???
    4 l* I! W: m. ]; ]如果是虚边最短距,也可以转化成实边最短距,然后结果一样的。4 T; U: b0 U) G4 \- k; K3 T' A
    =========================================
    5 U' X$ Z9 f' S0 A9 Z2 r
    " t$ S1 j5 N2 p2 {1 L; P' j: L/ R+ W  t1 R8 o
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-9-10 17:56 , Processed in 0.478935 second(s), 96 queries .

    回顶部