加载中…
个人资料
李恒星_释永思
李恒星_释永思
  • 博客等级:
  • 博客积分:0
  • 博客访问:31,395
  • 关注人气:67
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

关于弗洛伊德算法的严格数学证明(草稿3)

(2016-04-22 17:11:58)
关于弗洛伊德算法的严格数学证明(草稿3):
                     作者:李均宇(李恒星)  2016.04.22
                     http://www.okmyok.com/lisoft.htm   
经过弗洛伊德算法的三重循环后,任意两点之间的距离已是最短路。 
仍用数学归纳法,假设N <= n时,弗洛伊德算法是正确的,要证明,N = n+1时,弗洛伊德算法仍是成立的。 
设k = n+1是最后一点。 
任意两点间的最短距,如果是不经过k点的,显然floyd算法成立。
任意两点间AB的最短距,如果是经过k点的。
设路径为p=A....k....B,如果路径p中所有的顶点数P<=N,那么,把K点加入原顶点集合,把无关的顶点去掉,这三重循环就是N<=n的情形,所以弗洛伊德算法仍是成立的。
如果路径p中所有的顶点数P=N+1,那么这是一条直线来的,没有任何分支的。要证弗洛伊德算法成立,可能不难了。每处理一个顶点中间点,必是连接一个线段,所以弗洛伊德算法得证。
所以弗洛伊德算法成立。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有