分享
分销 收藏 举报 申诉 / 11

类型数学建模FLOYD算法.pptx

  • 上传人:天****
  • 文档编号:14231442
  • 上传时间:2026-07-23
  • 格式:PPTX
  • 页数:11
  • 大小:199.30KB
  • 下载积分:8 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    数学 建模 FLOYD 算法
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最短路径,Dijkstra,算法和,Floyd,算法,第1页,Dijkstra算法,1.定义概览,Dijkstra(迪杰斯特拉)算法是经典单源最短路径算法,用于计算一个节点到其它全部节点最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性最短路径算法,在很多专业课程中都作为基本内容有详细介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。,问题描述:在图 G=(V,E)中,假设每条边 Ei 长度为 wi,找到由顶点 V0 到其余各点最短路径。(单源最短路径),第2页,Floyd算法,1.定义概览,Floyd-Warshall算法,(Floyd-Warshall algorithm)是处理任意两点间最短路径一个算法,能够正确处理有向图或负权最短路径问题,同时也被用于计算有向图传递闭包。Floyd-Warshall算法时间复杂度为O(N3),空间复杂度为O(N2)。,第3页,2.算法描述,1)算法思想原理:,Floyd算法是一个经典动态规划算法。用通俗语言来描述话,首先我们目标是寻找从点i到点j最短路径。从动态规划角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力精华所在),第4页,从任意节点i到任意节点j最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v最短路径距离,对于每一个节点k,我们检验Dis(i,k)+Dis(k,j)Dis(i,j)是否成立,假如成立,证实从i到k再到j路径比i直接到j路径短,我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j),这么一来,当我们遍历完全部节点k,Dis(i,j)中统计便是i到j最短路径距离。,第5页,2).算法描述:,a.从任意一条单边路径开始。全部两点之间距离是边权,假如两点之间没有边相连,则权为无穷大。,b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知路径更短。假如是更新它。,第6页,%floyd算法通用程序,输入a为赋权邻接矩阵,%输出为距离矩阵D,和最短路径矩阵path,function D,path=floyd(a),n=size(a,1);,D=a;,path=zeros(n,n);,for i=1:n,for j=1:n,if D(i,j)=inf,path(i,j)=j;,end,end,end,for k=1:n,for i=1:n,for j=1:n,if D(i,k)+D(k,j)D(i,j),D(i,j)=D(i,k)+D(k,j);,path(i,j)=path(i,k);,end,end,end,end,第7页,第8页,第9页,第10页,第11页,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:数学建模FLOYD算法.pptx
    链接地址:https://www.zixin.com.cn/doc/14231442.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork