欢迎来到天天文库
浏览记录
ID:18543784
大小:174.50 KB
页数:7页
时间:2018-09-18
《数学建模实验报告最短路问题及其算法new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、最短路问题及其算法一.实验目的:1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法;2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.二.实验内容:要铺设一条A1→A2→…→A15的输送天然气的主管道,如图所示.经筛选后可以生产这种主管道的钢厂有S1,S2,…,S7.图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位:km).为方便计,1k
2、m主管道钢管称为1单位钢管.一个钢厂如果承担制造这种钢管,至少需要生产500单位钢厂在指定期限内能生产刚钢管的最大数量为个单位.钢管出厂销价1单位钢管为万元,如下表:1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表:里程(km)300301-350351-400401-450451-500运价(万元)2023262932里程(km)501-600601-700701-800801-900901-1000运价(万元)
3、37445055601000km以上每增加1至100km运价增加5万元.公路运输费用为1单位钢管0.1万元每千米(不足整千米部分按整千米计算).假设从钢厂订购钢管运输到铺设地点和.钢厂在指定期间内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为155万元.6试制定一个从钢厂到铺设地点和的钢管的订购与运输计划,使总费用最小.三.模型建立设为,将上图按从上到下,从右到左的顺序依次命名如下.将上图改为如下赋权图形:利用Dijkstra算法和Floyd算法:求中从顶点到其余顶点的最短路.而求钢厂到铺
4、设地点和的最短距离,即为到和的最短距离6解:先写出带权邻接矩阵:后分别用Dijkstra算法和Floyd算法步骤,求出到和的最短路的权以及的父亲点标记.四.模型求解(含经调试后正确的源程序)(1)Dijkstra算法road1.m文件源程序:w=[01200infinfinfinfinfinfinfinf;1200012202infinfinfinfinfinf;inf120inf201infinfinfinfinf;inf202inf03120infinfinfinf;infinf20131010
5、inf205infinf;infinfinf20100195infinfinf;infinfinfinfinf19505306inf;infinfinfinf205inf50inf194;infinfinfinfinfinf306inf010;infinfinfinfinfinfinf194100];n=size(w,1);w1=w(1,:);fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1;l;z;whilek6、:kifi~=s(j)ifl(i)>l(u)+w(u,i);l(i)=l(u)+w(u,i);z(i)=u;endendendendl;z;ll=l;fori=1:nforj=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;fori=1:nifll(i)7、nfinfinfinfinf;1200012202infinfinfinfinfinf;inf120inf201infinfinfinfinf;inf202inf03120infinfinfinf;infinf20131010inf205infinf;infinfinf20100195infinfinf;6infinfinfinfinf19505306inf;infinfinfinf205inf50inf194;infinfinfinfinfinf306inf010;infinfinfinfinfi8、nfinf194100];[D,R]=floyd(a)floyd.m文件源程序:function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)
6、:kifi~=s(j)ifl(i)>l(u)+w(u,i);l(i)=l(u)+w(u,i);z(i)=u;endendendendl;z;ll=l;fori=1:nforj=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;fori=1:nifll(i)7、nfinfinfinfinf;1200012202infinfinfinfinfinf;inf120inf201infinfinfinfinf;inf202inf03120infinfinfinf;infinf20131010inf205infinf;infinfinf20100195infinfinf;6infinfinfinfinf19505306inf;infinfinfinf205inf50inf194;infinfinfinfinfinf306inf010;infinfinfinfinfi8、nfinf194100];[D,R]=floyd(a)floyd.m文件源程序:function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)
7、nfinfinfinfinf;1200012202infinfinfinfinfinf;inf120inf201infinfinfinfinf;inf202inf03120infinfinfinf;infinf20131010inf205infinf;infinfinf20100195infinfinf;6infinfinfinfinf19505306inf;infinfinfinf205inf50inf194;infinfinfinfinfinf306inf010;infinfinfinfinfi
8、nfinf194100];[D,R]=floyd(a)floyd.m文件源程序:function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)
此文档下载收益归作者所有