请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 999|回复: 0

最短路问题

[复制链接]
字体大小: 正常 放大

1

主题

1

听众

6

积分

升级  1.05%

该用户从未签到

发表于 2018-6-6 11:32 |显示全部楼层
|招呼Ta 关注Ta
最短路问题及其算法
一.实验目的:
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
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2024-3-28 20:46 , Processed in 0.267667 second(s), 49 queries .

回顶部