数学建模实验报告 第十一章 最短路问题.doc

《数学建模实验报告 第十一章 最短路问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验名称：第十一章最短路问题一、实验内容与要求掌握Dijkstra算法和Floyd算法，并运用这两种算法求一些最短路径的问题。二、实验软件MATLAB7.0三、实验内容1、在一个城市交通系统中取出一段如图所示，其入口为顶点v1，出口为顶点v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为3，求v1到v8的最短时间路径。V11V23V31V56V6223V42V74V8程序：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;

2、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

3、8floy.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)>a=[0310infinfinfinfinf;30inf5infinfinfinf;10inf06infinfinfinf;inf5604inf10inf;infinfinf4095inf;infinfinfinf9034

4、;infinfinf105306;infinfinfinfinf460;];[D,R]=floyd(a)实验结果：D=0310InfInfInfInfInf30Inf5InfInfInfInf10Inf06InfInfInfInfInf5604Inf10InfInfInfInf4095InfInfInfInfInf9034InfInfInf105306InfInfInfInfInf460R=1234567812345678123456781234567812345678123456781234567812345678k=1D=0310InfInfInfInfInf30135Inf

5、InfInfInf101306InfInfInfInfInf5604Inf10InfInfInfInf4095InfInfInfInfInf9034InfInfInf105306InfInfInfInfInf460R=1234567812145678113456781234567812345678123456781234567812345678k=2D=03108InfInfInfInf30135InfInfInfInf101306InfInfInfInf85604Inf10InfInfInfInf4095InfInfInfInfInf9034InfInfInf105306Inf

6、InfInfInfInf460R=1232567812145678113456782234567812345678123456781234567812345678k=3D=03108InfInfInfInf30135InfInfInfInf101306InfInfInfInf85604Inf10InfInfInfInf4095InfInfInfInfInf9034InfInfInf105306InfInfInfInfInf460R=1232567812145678113456782234567812345678123456781234567812345678k=4D=031081

7、2Inf18Inf301159Inf15Inf10110610Inf16Inf85604Inf10Inf129104095InfInfInfInfInf9034181516105306InfInfInfInfInf460R=1232262812444648143446482234567844445678123456784444567812345678k=5D=03108122117Inf3011591814Inf101106101915Inf85604139Inf12910409