第8讲最短路问题实验.ppt
《第8讲最短路问题实验.ppt》由会员分享,可在线阅读,更多相关《第8讲最短路问题实验.ppt(28页珍藏版)》请在三一文库上搜索。
1、数学模型与数学实验,图论模型,实验目的,实验内容,2、会用Matlab软件求最短路,1、了解最短路的算法及其应用,1、图 论 的 基 本 概 念,2、最 短 路 问 题 及 其 算 法,3、最 短 路 的 应 用,4、实验作业,固 定 起 点 的 最 短 路,最短路是一条路径,且最短路的任一段也是最短路,假设在u0-v0的最短路中只取一条,则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路,算法步骤:,u1,u2,u3,u4,u5,u6,u7,u8,w= ; function l,z=Dijkstra(W) n = size (W,1)
2、; for i = 1 :n l(i)=W(1,i); z(i)=1; end i=1; while i=n for j =1 :n,if l(i)l(j)+W(j,i) l(i)=l(j)+W(j,i); z(i)=j; if ji i=j-1; end end end i=i+1; end,floyd算法的基本思想,算法原理 求距离矩阵的方法,算法原理 求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R,即当vk被插入任何两点间的最短路径时,被记录在R(k)中,依次求 时求得 ,可由 来查找任何点对之间最短路的路径,算法原理 查找最短路路径的方法,pk,p2,p1,p3,q1,q2,q
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 短路 问题 实验
链接地址:https://www.31doc.com/p-2980829.html