- 在线时间
- 0 小时
- 最后登录
- 2018-6-6
- 注册时间
- 2018-6-6
- 听众数
- 1
- 收听数
- 0
- 能力
- 0 分
- 体力
- 8 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 6
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 6
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 1
升级 1.05% 该用户从未签到
|
最短路问题及其算法
一.实验目的:
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法;
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
二.实验内容:
要铺设一条A1→A2→…→A15的输送天然气的主管道,如图所示.经筛选后可以生产这种主管道的钢厂有S1,S2,…,S7.图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位:km).
为方便计,1km主管道钢管称为1单位钢管.
一个钢厂如果承担制造这种钢管,至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元,如下表:
1 2 3 4 5 6 7
800 800 1000 2000 2000 2000 3000
160 155 155 160 155 150 160
1单位钢管的铁路运价如下表:
里程(km) 300
301-350 351-400 401-450 451-500
运价(万元) 20 23 26 29 32
里程(km) 501-600 601-700 701-800 801-900 901-1000
运价(万元) 37 44 50 55 60
1000km以上每增加1至100km运价增加5万元.
公路运输费用为1单位钢管0.1万元每千米(不足整千米部分按整千米计算).
假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位,钢管出厂销价1单位钢管为155万元.
试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划,使总费用最小.
三. 模型建立
设 为 ,将上图按从上到下,从右到左的顺序依次命名如下.将上图改为如下赋权图形 :
利用Dijkstra算法和Floyd算法:求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离,即为 到 和 的最短距离
解:先写出带权邻接矩阵:
后分别用Dijkstra算法和Floyd算法步骤,求出 到 和 的最短路的权 以及 的父亲点标记 .
四. 模型求解(含经调试后正确的源程序)
(1) Dijkstra算法
road1.m文件源程序:
w=[0 1200 inf inf inf inf inf inf inf inf;
1200 0 12 202 inf inf inf inf inf inf;
inf 12 0 inf 201 inf inf inf inf inf;
inf 202 inf 0 31 20 inf inf inf inf;
inf inf 201 31 0 10 inf 205 inf inf;
inf inf inf 20 10 0 195 inf inf inf;
inf inf inf inf inf 195 0 5 306 inf;
inf inf inf inf 205 inf 5 0 inf 194;
inf inf inf inf inf inf 306 inf 0 10;
inf inf inf inf inf inf inf 194 10 0];
n=size(w,1);
w1=w(1,;
for i=1:n
l(i)=w1(i);
z(i)=1;
end
s=[];
s(1)=1;
u=s(1);
k=1;
l;
z;
while k<n
for i=1:n
for j=1:k
if i~=s(j)
if l(i)>l(u)+w(u,i);
l(i)=l(u)+w(u,i);
z(i)=u;
end
end
end
end
l;
z;
ll=l;
for i=1:n
for j=1:k
if i~=s(j)
ll(i)=ll(i);
else
ll(i)=inf;
end
end
end
lv=inf;
for i=1:n
if ll(i)<lv
lv=ll(i);
v=i;
end
end
lv;
v;
s(k+1)=v;
k=k+1;
u=s(k);
end
l
z
(2) Floyd算法
road2.m文件源程序:
a=[0 1200 inf inf inf inf inf inf inf inf;
1200 0 12 202 inf inf inf inf inf inf;
inf 12 0 inf 201 inf inf inf inf inf;
inf 202 inf 0 31 20 inf inf inf inf;
inf inf 201 31 0 10 inf 205 inf inf;
inf inf inf 20 10 0 195 inf inf inf;
inf inf inf inf inf 195 0 5 306 inf;
inf inf inf inf 205 inf 5 0 inf 194;
inf inf inf inf inf inf 306 inf 0 10;
inf inf inf inf inf inf inf 194 10 0];
[D,R]=floyd(a)
floyd.m文件源程序:
function[D,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
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
R(i,j)=R(i,k);
end
end
end
k
D
R
end
五.结果分析
(1)Dijkstra算法
运行结果:
l = 0 1200 1212 1402 1413 1422 1617 1618 1822 1812
z =1 1 2 2 3 4 6 5 10 8
结果分析:
通过运行结果: 到其他顶点的最短路的权 ,可看出,
到 (即 到 )的最短距离为1812(km);
到 (即 到 )的最短距离为1618(km);
到 的最短路径为:V1→V2→V3→V5→V8→V10;
到 的最短路径为:V1→V2→V3→V5→V8。
(2) Floyd算法
运行结果:
D =
0 1200 1212 1402 1413 1422 1617 1618 1822 1812
1200 0 12 202 213 222 417 418 622 612
1212 12 0 214 201 211 406 406 610 600
1402 202 214 0 30 20 215 220 424 414
1413 213 201 30 0 10 205 205 409 399
1422 222 211 20 10 0 195 200 404 394
1617 417 406 215 205 195 0 5 209 199
1618 418 406 220 205 200 5 0 204 194
1822 622 610 424 409 404 209 204 0 10
1812 612 600 414 399 394 199 194 10 0
R =
1 2 2 2 2 2 2 2 2 2
1 2 3 4 3 4 4 3 3 3
2 2 3 2 5 5 5 5 5 5
2 2 2 4 6 6 6 6 6 6
3 3 3 6 5 6 6 8 8 8
4 4 5 4 5 6 7 7 7 7
6 6 6 6 6 6 7 8 8 8
5 5 5 7 5 7 7 8 10 10
10 10 10 10 10 10 10 10 9 10
8 8 8 8 8 8 8 8 9 10
结果分析:
通过运行结果:可看出,
到 (即 到 )的最短距离为1812(km);
到 的最短路径为:V1→V2→V3→V5→V8→V10;
到 (即 到 )的最短距离为1618(km);
到 的最短路径为:V1→V2→V3→V5→V8。
|
zan
|