版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、湖南大学 湖南大学 MATLAB实训报告 题 目: matlab计算最短路径问题 学院名称:信息科学与工程学院 专业班级: 软件工程四班 学生姓名: 彭天越 学 号: 20112601416 日 期: 2013年7月3号 目录题目2问题描述3(1)根据无向图A,使用Di.jistra算法3(2)根据有向图B,使用Warshall-Floyd算法3思路及代码3(1)思路3(2)源代码4测试结果说明9(1)Di.jistra算法9(2)Floyd算法10小结10题目求下图中顶点1到顶点11的最短距离和最短路(2学分) B.有向图问题描述(1)根据无向图A,使用Di.jistra算法(2)根据有向图
2、B,使用Warshall-Floyd算法思路及代码(1)思路(1)Dijkstra算法使用范围:1) 寻求从一固定顶点到其余各点的最短路径;2) 有向图、无向图和混合图;3) 权非负.算法思路: 采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径.诉法步骤:S: 具有永久标号的顶点集;l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=w(vi,vj)nxm.1) 初始化 令l(v0)=0,S=F; vv0 ,l(v)=;2) 更新l(v), f(v) 寻找不在S中的顶点u,使
3、l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)l(u)+w(u,v),则更新l(v),f(v), 即 l(v)l(u)+w(u,v),f(v)u;3) 重复步骤2), 直到所有顶点都在S中为止.(2)Floyd算法使用范围:1) 求每对顶点的最短路径;2) 有向图、无向图和混合图;算法思想: 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), , D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径.算法步骤:d(i,j) : i到j的距离; path(i,j): i到j的路径上i的后继点; 输入带权邻接矩
4、阵a(i,j).1)赋初值 对所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2)更新d(i,j) , path(i,j) 对所有i,j, 若d(i,k)+d(k,j)d(i,j),则 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+13)重复2)直到k=n+1(2)源代码(1)Dijkstra.m文件%计算最短路径(Dijkstra算法)%min表示最短的距离%path表示最短路径%w表示邻接矩阵%start表示开始点%terminal表示终止点function min,path=dijkstra(w,start,ter
5、minal)n=size(w,1); %计算邻接矩阵的行数label(start)=0; f(start)=start;%初始化for i=1:n if i=start label(i)=inf; endends(1)=start; u=start;%更新最短路径直到所有顶点都遍历while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,v); f(v)=u; end end end %v1=0; k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end end if ins
6、=0 v=i; if klabel(v) k=label(v); v1=v; end end end s(length(s)+1)=v1; u=v1;end%求出最短距离与最短路径min=label(terminal); path(1)=terminal;i=1; while path(i)=start path(i+1)=f(path(i); i=i+1 ;end path(i)=start;L=length(path);path=path(L:-1:1);%循环输出路径text01.m脚本文件进行测试clear;clc;fprintf(计算最短路径(Dijkstra算法)n); x=0,2
7、,1,8,inf,inf,inf,inf,inf,inf,inf;2,0,inf,6,1,inf,inf,inf,inf,inf,inf;1,inf,0,7,inf,inf,9,inf,inf,inf,inf;8,6,7,0,5,1,2,inf,inf,inf,inf;inf,1,inf,5,0,3,inf,2,1,inf,inf;inf,inf,inf,1,3,0,4,inf,6,inf,inf;inf,inf,9,2,inf,4,0,inf,3,1,inf;inf,inf,inf,inf,2,inf,inf,0,7,inf,inf;inf,inf,inf,inf,inf,6,3,7,0,1
8、,2;inf,inf,inf,inf,inf,inf,1,inf,1,0,1;inf,inf,inf,inf,inf,inf,inf,inf,2,1,0%x=input(输入邻接矩阵:);start=input(输入起点:);terminal=input(输入终点:);fprintf(计算结果如下:);min,path_way=dijkstra(x,start,terminal)Floyd.m函数%计算最短路径(Floyd算法)%D,path,min1,path1=floyd(a,start,terminal)返回矩阵D, path; 并返回start与terminal之间的最短距离min1和
9、最短路径path1.%path(i,j): 表示i到j的路径上i的后继点;%D(i,j) : 表示i到j的距离;%输入带权邻接矩阵a(i,j).%1)赋初值% 对所有i,j, D(i,j)-a(i,j) , path(i,j)-j%2)更新D(i,j) , path(i,j)% 对所有i,j, 若D(i,k)+D(k,j)d(i,j),则% D(i,j)-D(i,k)+D(k,j) , path(i,j)-path(i,k) , k-k+1%3)重复2)直到k=n+1function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1
10、);path=zeros(n,n);%初始化for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor 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 endendif nargin=3%参数个数为3的时候执行 min1=D(start,terminal);%最短距离 m(1)=start; i=1; path1= ; %计算最短路径 while path(m(i),terminal
11、)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end text02.m脚本文件,进行测试clear;clc;fprintf(计算最短路径(Floyd算法)n); x=0,2,inf,8,inf,inf,inf,inf,inf,inf,inf;inf,0,inf,6,1,inf,inf,inf,inf,inf,inf;1,inf,0,inf,inf,inf,9,inf,inf,inf,inf;inf,inf,7,0,inf,inf,inf,inf,inf,inf,inf;inf,in
12、f,inf,5,0,inf,inf,inf,1,inf,inf;inf,inf,inf,1,3,0,4,inf,inf,inf,inf;inf,inf,inf,2,inf,inf,0,inf,3,1,inf;inf,inf,inf,inf,2,inf,inf,0,inf,inf,inf;inf,inf,inf,inf,inf,6,inf,7,0,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,1,0,1;inf,inf,inf,inf,inf,inf,inf,inf,2,inf,0%x=input(输入邻接矩阵:);start=input(输入起点:);terminal=input(输入终点:);fprintf(计算结果如下:);D,path,min,path_way=floyd(x,start,terminal)测试结果说明(1)Di.jistra算法根据无向图A,可以知道matlab计算出来的结果是正确的(2)Floyd算法根据有向图B,可以知道matlab计算出来的结果是正确的小结Matlab 现在的发展
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年道路运输服务项目资金筹措计划书代可行性研究报告
- 2023年汽、柴油深度加氢催化剂投资申请报告
- 2024年烟度计项目投资申请报告代可行性研究报告
- 十字相乘法课件
- 《故事口才故事会》课件
- 消防知识国旗下讲话稿(33篇)
- 门面房租赁合约合同(31篇)
- 社区环境调查报告
- 四川省遂宁市蓬溪县2024届九年级上学期期末考试数学试卷(含答案)
- 贵州省六盘水市2023-2024学年高二上学期1月期末质量监测试题 数学 含答案
- 【MOOC】国际商务-暨南大学 中国大学慕课MOOC答案
- 2024年“新华三杯”全国大学生数字技术大赛备赛试题库(含答案)
- 2024年新课标培训2022年小学英语新课标学习培训课件
- 人教版(2024新版)七年级上册生物期末复习全册知识点提纲
- 2024新版有限空间作业安全大培训
- 创业实务智慧树知到期末考试答案章节答案2024年山东大学
- 万能中国地图模板(可修改)
- 框架结构内力计算-竖向弯矩二次分配,水平D值法讲解
- 《初中团队一体化工作模式的实践与研究》
- 工程增项签证单样本
- 餐饮消防安全培训(完整版)
评论
0/150
提交评论