数学建模案例分析最短路问题.pptx
《数学建模案例分析最短路问题.pptx》由会员分享,可在线阅读,更多相关《数学建模案例分析最短路问题.pptx(38页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、2023/2/14实验目的实验内容2会用MATLAB软件求最短路1了解最短路的算法及其应用1图 论 的 基 本 概 念2最 短 路 问 题 及 其 算 法3最 短 路 的 应 用4建模案例:最优截断切割问题5实验作业第1页/共38页2023/2/14图 论 的 基 本 概 念一、图 的 概 念1图的定义2顶点的次数 3子图二、图 的 矩 阵 表 示1 关联矩阵2 邻接矩阵返回第2页/共38页2023/2/14定义有序三元组G=(V,E,)称为一个图,如果:图的定义图的定义第3页/共38页2023/2/14定义定义第4页/共38页2023/2/14第5页/共38页2023/2/14返回第6页/共
2、38页2023/2/14顶点的次数顶点的次数第7页/共38页2023/2/14例 在一次聚会中,认识奇数个人的人数一定是偶数.返回第8页/共38页2023/2/14子图子图返回第9页/共38页2023/2/14关联矩阵关联矩阵注:假设图为简单图返回第10页/共38页2023/2/14邻接矩阵邻接矩阵注:假设图为简单图第11页/共38页2023/2/14返回第12页/共38页2023/2/14最 短 路 问 题 及 其 算 法一、基 本 概 念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路返回第13页/共38页2023/2/14基基 本本 概概 念念第14页/共38
3、页2023/2/14返回第15页/共38页2023/2/14固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径,且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条,则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路第16页/共38页2023/2/14第17页/共38页2023/2/14算法步骤:第18页/共38页2023/2/14 TO MATLAB(road1)第19页/共38页2023/2/14第20页/共38页2023/2/14 1 2 34 5 6 7 8返回第21页/共38页2023/2/14每每 对对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 案例 分析 短路 问题
限制150内