第8讲最短路问题ppt课件.ppt
《第8讲最短路问题ppt课件.ppt》由会员分享,可在线阅读,更多相关《第8讲最短路问题ppt课件.ppt(38页珍藏版)》请在三一文库上搜索。
1、数学建模与数学实验,后勤工程学院数学教研室,最短路问题,实验目的,实验内容,2、会用Matlab软件求最短路,1、了解最短路的算法及其应用,1、图 论 的 基 本 概 念,2、最 短 路 问 题 及 其 算 法,3、最 短 路 的 应 用,4、建模案例:最优截断切割问题,5、实验作业,图 论 的 基 本 概 念,一、 图 的 概 念,1、图的定义,2、顶点的次数,3、子图,二、 图 的 矩 阵 表 示,1、 关联矩阵,2、 邻接矩阵,返回,图的定义,定义,定义,返回,顶点的次数,例 在一次聚会中,认识奇数个人的人数一定是偶数。,返回,子图,返回,关联矩阵,注:假设图为简单图,返回,邻接矩阵,注
2、:假设图为简单图,返回,最 短 路 问 题 及 其 算 法,一、 基 本 概 念,二、固 定 起 点 的 最 短 路,三、每 对 顶 点 之 间 的 最 短 路,返回,基 本 概 念,返回,固 定 起 点 的 最 短 路,最短路是一条路径,且最短路的任一段也是最短路,假设在u0-v0的最短路中只取一条,则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路,算法步骤:,TO MATLAB (road1),u1,u2,u3,u4,u5,u6,u7,u8,返回,每 对 顶 点 之 间 的 最 短 路,1、求距离矩阵的方法,2、求路径矩阵的方法,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 短路 问题 ppt 课件
链接地址:https://www.31doc.com/p-2502105.html