《数学建模实验报告第十一章最短路问题.pdf》由会员分享，可在线阅读，更多相关《数学建模实验报告第十一章最短路问题.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、其身正，不令而行；其身不正，虽令不从。论语好学近乎知，力行近乎仁，知耻近乎勇。中庸 一、实验内容与要求 掌握 Dijkstra 算法和 Floyd 算法，并运用这两种算法求一些最短路径的问题。二、实验软件 三、实验内容 1、在一个城市交通系统中取出一段如图所示，其入口为顶点 v1，出口为顶点 v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为 3，求 v1到 v8的最短时间路径。V1 1 V2 3 V3 1 V5 6 V6 3 V4 2 V7 4 V8 程序：function y=bijiaodaxiao(f1,f2,f3,f4)v12=1;v23=3;v24=2;v35=1
2、;v47=2;v57=2;v56=6;v68=3;v78=4;turn=3;f1=v12+v23+v35+v56+turn+v68;2 2 忍一句，息一怒，饶一着，退一步。增广贤文勿以恶小而为之，勿以善小而不为。刘备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;if f2min min=f2;end if f3min min=f3;end if f4min min=f4;end min f1 f2 f3 f4
3、实验结果：v1到 v8的最短时间路径为 15，路径为 1-2-4-7-8.穷则独善其身，达则兼善天下。孟子一寸光阴一寸金，寸金难买寸光阴。增广贤文 2、求如图所示中每一结点到其他结点的最短路。V1 10 V3 V5 9 V6 4 V2 5 V4 10 V7 6 V8 中的程序：functionD,R=floyd(a)n=size(a,1);D=a for i=1:n for j=1:n R(i,j)=j;end end R for k=1:n for i=1:n 3 6 4 5 3 百川东到海，何时复西归？少壮不尽力，老大徒伤悲。汉乐府长歌行非淡泊无以明志，非宁静无以致远。诸葛亮 for j=
4、1:n if D(i,k)+D(k,j)a=0 3 10 inf inf inf inf inf;3 0 inf 5 inf inf inf inf;10 inf 0 6 inf inf inf inf;inf 5 6 0 4 inf 10 inf;inf inf inf 4 0 9 5 inf;inf inf inf inf 9 0 3 4;inf inf inf 10 5 3 0 6;inf inf inf inf inf 4 6 0;D,R=floyd(a)人不知而不愠，不亦君子乎？论语万两黄金容易得，知心一个也难求。曹雪芹 实验结果：D=0 3 10 Inf Inf Inf Inf I
5、nf 3 0 Inf 5 Inf Inf Inf Inf 10 Inf 0 6 Inf Inf Inf Inf Inf 5 6 0 4 Inf 10 Inf Inf Inf Inf 4 0 9 5 Inf Inf Inf Inf Inf 9 0 3 4 Inf Inf Inf 10 5 3 0 6 Inf Inf Inf Inf Inf 4 6 0 R=1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 常将有日思无日，莫待无时思有时。增广贤文忍一句，息一
6、怒，饶一着，退一步。增广贤文 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 k=1 D=0 3 10 Inf Inf Inf Inf Inf 3 0 13 5 Inf Inf Inf Inf 10 13 0 6 Inf Inf Inf Inf Inf 5 6 0 4 Inf 10 Inf Inf Inf Inf 4 0 9 5 Inf Inf Inf Inf Inf 9 0 3 4 Inf Inf Inf 10 5 3 0 6 Inf Inf Inf Inf Inf 4 6 0 R=人不知而不愠，不亦君子乎？论语百学须先立志。朱熹 1 2 3 4 5 6 7 8 1 2 1
7、4 5 6 7 8 1 1 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 k=2 D=0 3 10 8 Inf Inf Inf Inf 3 0 13 5 Inf Inf Inf Inf 10 13 0 6 Inf Inf Inf Inf 8 5 6 0 4 Inf 10 Inf 人人好公，则天下太平；人人营私，则天下大乱。刘鹗人不知而不愠，不亦君子乎？论语 Inf Inf Inf 4 0 9 5 Inf Inf Inf Inf Inf 9 0 3 4 Inf
8、 Inf Inf 10 5 3 0 6 Inf Inf Inf Inf Inf 4 6 0 R=1 2 3 2 5 6 7 8 1 2 1 4 5 6 7 8 1 1 3 4 5 6 7 8 2 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 k=3 其身正，不令而行；其身不正，虽令不从。论语百川东到海，何时复西归？少壮不尽力，老大徒伤悲。汉乐府长歌行 D=0 3 10 8 Inf Inf Inf Inf 3 0 13 5 Inf Inf Inf Inf 10 13 0 6 Inf In
9、f Inf Inf 8 5 6 0 4 Inf 10 Inf Inf Inf Inf 4 0 9 5 Inf Inf Inf Inf Inf 9 0 3 4 Inf Inf Inf 10 5 3 0 6 Inf Inf Inf Inf Inf 4 6 0 R=1 2 3 2 5 6 7 8 1 2 1 4 5 6 7 8 1 1 3 4 5 6 7 8 2 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武人人好公，则天下太平；人人营私，则天
10、下大乱。刘鹗 1 2 3 4 5 6 7 8 k=4 D=0 3 10 8 12 Inf 18 Inf 3 0 11 5 9 Inf 15 Inf 10 11 0 6 10 Inf 16 Inf 8 5 6 0 4 Inf 10 Inf 12 9 10 4 0 9 5 Inf Inf Inf Inf Inf 9 0 3 4 18 15 16 10 5 3 0 6 Inf Inf Inf Inf Inf 4 6 0 R=百学须先立志。朱熹其身正，不令而行；其身不正，虽令不从。论语 1 2 3 2 2 6 2 8 1 2 4 4 4 6 4 8 1 4 3 4 4 6 4 8 2 2 3 4 5
11、6 7 8 4 4 4 4 5 6 7 8 1 2 3 4 5 6 7 8 4 4 4 4 5 6 7 8 1 2 3 4 5 6 7 8 k=5 D=0 3 10 8 12 21 17 Inf 3 0 11 5 9 18 14 Inf 10 11 0 6 10 19 15 Inf 8 5 6 0 4 13 9 Inf 12 9 10 4 0 9 5 Inf 勿以恶小而为之，勿以善小而不为。刘备吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语 21 18 19 13 9 0 3 4 171*5306 Inf Inf Inf Inf Inf 4 6 0 R=1 2 3 2 2 2
12、 2 8 1 2 4 4 4 4 4 8 1 4 3 4 4 4 4 8 2 2 3 4 5 5 5 8 4 4 4 4 5 6 7 8 5 5 5 5 5 6 7 8 5 5 5 5 5 6 7 8 1 2 3 4 5 6 7 8 k=6 非淡泊无以明志，非宁静无以致远。诸葛亮忍一句，息一怒，饶一着，退一步。增广贤文D=0 3 10 8 12 21 17 25 3 0 11 5 9 18 14 22 10 11 0 6 10 19 15 23 8 5 6 0 4 13 9 17 12 9 10 4 0 9 5 13 21 18 19 13 9 0 3 4 171*5306 25 22 23
13、17 13 4 6 0 R=1 2 3 2 2 2 2 2 1 2 4 4 4 4 4 4 1 4 3 4 4 4 4 4 2 2 3 4 5 5 5 5 4 4 4 4 5 6 7 6 5 5 5 5 5 6 7 8 5 5 5 5 5 6 7 8 6 6 6 6 6 6 7 8 百学须先立志。朱熹非淡泊无以明志，非宁静无以致远。诸葛亮 k=7 D=0 3 10 8 12 20 17 23 3 0 11 5 9 17 14 20 10 11 0 6 10 18 15 21 8 5 6 0 4 12 9 15 12 9 10 4 0 8 5 11 20 17 18 12 8 0 3 4 171
14、*5306 23 20 21 15 11 4 6 0 R=1 2 3 2 2 2 2 2 丹青不知老将至，贫贱于我如浮云。杜甫老当益壮，宁移白首之心；穷且益坚，不坠青云之志。唐王勃 1 2 4 4 4 4 4 4 1 4 3 4 4 4 4 4 2 2 3 4 5 5 5 5 4 4 4 4 5 7 7 7 7 7 7 7 7 6 7 8 5 5 5 5 5 6 7 8 7 7 7 7 7 6 7 8 k=8 D=0 3 10 8 12 20 17 23 3 0 11 5 9 17 14 20 10 11 0 6 10 18 15 21 8 5 6 0 4 12 9 15 12 9 10 4
15、0 8 5 11 20 17 18 12 8 0 3 4 丹青不知老将至，贫贱于我如浮云。杜甫天行健，君子以自强不息。地势坤，君子以厚德载物。易经171*5306 23 20 21 15 11 4 6 0 R=1 2 3 2 2 2 2 2 1 2 4 4 4 4 4 4 1 4 3 4 4 4 4 4 2 2 3 4 5 5 5 5 4 4 4 4 5 7 7 7 7 7 7 7 7 6 7 8 5 5 5 5 5 6 7 8 7 7 7 7 7 6 7 8 D=0 3 10 8 12 20 17 23 3 0 11 5 9 17 14 20 10 11 0 6 10 18 15 21 8 5 6 0 4 12 9 15 以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。旧唐书魏征列传人人好公，则天下太平；人人营私，则天下大乱。刘鹗 12 9 10 4 0 8 5 11 20 17 18 12 8 0 3 4 171*5306 23 20 21 15 11 4 6 0 R=1 2 3 2 2 2 2 2 1 2 4 4 4 4 4 4 1 4 3 4 4 4 4 4 2 2 3 4 5 5 5 5 4 4 4 4 5 7 7 7 7 7 7 7 7 6 7 8 5 5 5 5 5 6 7 8 7 7 7 7 7 6 7 8 四、实验体会