数学建模实验报告第十一章最短路问题.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;
iff2min=f2;
end
iff3min=f3;
end
iff4min=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
四、实验体会
升级会员 