数学建模实验报告第十一章最短路问题.docx
- 文档编号:13759992
- 上传时间:2023-06-17
- 格式:DOCX
- 页数:12
- 大小:15.41KB
数学建模实验报告第十一章最短路问题.docx
《数学建模实验报告第十一章最短路问题.docx》由会员分享,可在线阅读,更多相关《数学建模实验报告第十一章最短路问题.docx(12页珍藏版)》请在冰点文库上搜索。
数学建模实验报告第十一章最短路问题
一、实验内容与要求
掌握Dijkstra算法和Floyd算法,并运用这两种算法求一些最短路径的问题。
二、实验软件
三、实验内容
1、在一个城市交通系统中取出一段如图所示,其入口为顶点v1,出口为顶点v8,每条弧段旁的数字表示通过该路段所需时间,每次转弯需要附加时间为3,求v1到v8的最短时间路径。
V11V23V31V56V6
2
2
3
V42V74V8
程序:
functiony=bijiaodaxiao(f1,f2,f3,f4)
v12=1;v23=3;v24=2;v35=1;v47=2;v57=2;v56=6;v68=3;v78=4;turn=3;
f1=v12+v23+v35+v56+turn+v68;
f2=v12+v23+v35+turn+v57+turn+v78;
f3=v12+turn+v24+turn+v47+v78;
f4=v12+turn+v24+v47+turn+v57+turn+v56+turn+v68;
min=f1;
iff2 min=f2; end iff3 min=f3; end iff4 min=f4; end min f1 f2 f3 f4 实验结果: v1到v8的最短时间路径为15,路径为1-2-4-7-8. 2、求如图所示中每一结点到其他结点的最短路。 V110V3V59V6 3 64 53 4 V25V410V76V8 中的程序: function[D,R]=floyd(a) n=size(a,1); D=a fori=1: n forj=1: n R(i,j)=j; end end R fork=1: n fori=1: n forj=1: n ifD(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D R end 程序: >>a=[0310infinfinfinfinf;30inf5infinfinfinf;10inf06infinfinfinf;inf5604inf10inf; infinfinf4095inf;infinfinfinf9034;infinfinf105306;infinfinfinfinf460;]; [D,R]=floyd(a) 实验结果: D= 0310InfInfInfInfInf 30Inf5InfInfInfInf 10Inf06InfInfInfInf Inf5604Inf10Inf InfInfInf4095Inf InfInfInfInf9034 InfInfInf105306 InfInfInfInfInf460 R= 12345678 12345678 12345678 12345678 12345678 12345678 12345678 12345678 k= 1 D= 0310InfInfInfInfInf 30135InfInfInfInf 101306InfInfInfInf Inf5604Inf10Inf InfInfInf4095Inf InfInfInfInf9034 InfInfInf105306 InfInfInfInfInf460 R= 12345678 12145678 11345678 12345678 12345678 12345678 12345678 12345678 k= 2 D= 03108InfInfInfInf 30135InfInfInfInf 101306InfInfInfInf 85604Inf10Inf InfInfInf4095Inf InfInfInfInf9034 InfInfInf105306 InfInfInfInfInf460 R= 12325678 12145678 11345678 22345678 12345678 12345678 12345678 12345678 k= 3 D= 03108InfInfInfInf 30135InfInfInfInf 101306InfInfInfInf 85604Inf10Inf InfInfInf4095Inf InfInfInfInf9034 InfInfInf105306 InfInfInfInfInf460 R= 12325678 12145678 11345678 22345678 12345678 12345678 12345678 12345678 k= 4 D= 0310812Inf18Inf 301159Inf15Inf 10110610Inf16Inf 85604Inf10Inf 129104095Inf InfInfInfInf9034 181516105306 InfInfInfInfInf460 R= 12322628 12444648 14344648 22345678 44445678 12345678 44445678 12345678 k= 5 D= 03108122117Inf 3011591814Inf 101106101915Inf 85604139Inf 129104095Inf 211819139034 17141595306 InfInfInfInfInf460 R= 12322228 12444448 14344448 22345558 44445678 55555678 55555678 12345678 k= 6 D= 0310812211725 301159181422 10110610191523 8560413917 12910409513 211819139034 17141595306 2522231713460 R= 12322222 12444444 14344444 22345555 44445676 55555678 55555678 66666678 k= 7 D= 0310812201723 301159171420 10110610181521 8560412915 12910408511 201718128034 17141595306 2320211511460 R= 12322222 12444444 14344444 22345555 44445777 77777678 55555678 77777678 k= 8 D= 0310812201723 301159171420 10110610181521 8560412915 12910408511 201718128034 17141595306 2320211511460 R= 12322222 12444444 14344444 22345555 44445777 77777678 55555678 77777678 D= 0310812201723 301159171420 10110610181521 8560412915 12910408511 201718128034 17141595306 2320211511460 R= 12322222 12444444 14344444 22345555 44445777 77777678 55555678 77777678 四、实验体会
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 实验 报告 第十一 短路 问题