最短路问题

2395960434

最短路问题及其算法
一.实验目的：
0 [' ^( {! B8 ^5 v' c% E1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
( }; E4 t; |, P# a4 t二.实验内容：
要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.
为方便计，1km主管道钢管称为1单位钢管.
+ L7 l' J  ~3 j: T9 P% `1 B0 |一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元，如下表：

4 ~4 I5 n7 `( Q0 z  b1        2        3        4        5        6        7
7 j; O( k2 r7 Q& `5 O$ Y: F6 b+ n
800        800        1000        2000        2000        2000        3000
# r: N5 [( A$ X8 q* W5 Z- R
160        155        155        160        155        150        160
. t" l' k+ l  R! L' n- a
1单位钢管的铁路运价如下表：
, ?! a) X; [% M2 ^. R  I  y里程（km）          300
* P1 l; t9 l, w/ J- g301-350        351-400        401-450        451-500
运价（万元）        20          23          26          29          32
0 s4 ?" {7 w2 _' f* O% _里程（km）        501-600        601-700        701-800        801-900        901-1000
运价（万元）          37          44          50          55          60
# f  u4 G/ V! }; |: u1 B1000km以上每增加1至100km运价增加5万元.
$ j9 T8 O6 c: U6 [3 ]( a5 R公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.
1 j# G, o2 F/ R, E6 ?) Z. K4 L1 L假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为155万元.

试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划，使总费用最小.
三. 模型建立
设 为 ,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形 ：

; y8 x/ L9 |& A" F利用Dijkstra算法和Floyd算法：求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离，即为 到 和 的最短距离

) L; m3 A  q. z; e解：先写出带权邻接矩阵：

: |, X9 H& U3 f后分别用Dijkstra算法和Floyd算法步骤，求出 到 和 的最短路的权 以及 的父亲点标记 .
( [8 _3 s8 f/ k9 {" t8 d' ^/ k& k4 j四. 模型求解（含经调试后正确的源程序）
(1) Dijkstra算法
road1.m文件源程序：
( a; @9 [5 U1 z+ Y3 }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;
( o1 e& {! c) p2 W2 einf 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];
2 X# f  x2 T7 s$ A2 @0 zn=size(w,1);
w1=w(1,;
for i=1:n
    l(i)=w1(i);
4 |9 N. R/ n0 Q1 a! b& J& c. f& b    z(i)=1;
% l) h& Z3 M0 E% p. ]2 iend
s=[];
s(1)=1;
9 ]% S4 g: Q. `7 {! ?3 l! H: eu=s(1);
k=1;
l;
$ i6 x5 C$ y. z) n. iz;
2 @; a. Z2 x. M9 B  \while k<n
" A8 |, J9 \7 X. m    for i=1:n
6 ^) A+ N$ @6 O, d. w7 z) l% T3 J    for j=1:k
       if i~=s(j)
          if l(i)>l(u)+w(u,i);
             l(i)=l(u)+w(u,i);
* h( b$ a; O  M             z(i)=u;
7 {8 H) J4 k% l: |) d- f3 ^         end
     end
/ _, k! H; Q+ Q) y* F. A, O7 N end
end
8 R& s6 k. I5 X0 R l;
- @1 b  F( n, H- ^ z;
, s$ Z2 j2 J6 h) i8 X! bll=l;
for i=1:n
( L6 Z+ _! n. Q6 w* b for j=1:k
    if i~=s(j)
- p9 x+ B3 \2 S9 ~" d3 b7 L       ll(i)=ll(i);
! \: E2 L9 r5 m! r5 N8 _   else
: \$ q  H, N, j" K/ x. t. ~6 h2 i       ll(i)=inf;
) @( L) S) r4 S" g1 [) z; r+ G1 a   end
end
end
lv=inf;
for i=1:n
/ }' T' q5 t$ D6 M$ `+ D/ d    if ll(i)<lv
       lv=ll(i);
$ m: ?4 _% Z/ O3 y       v=i;
   end
end
lv;
8 ]* y6 q: F+ N5 n3 Y9 `" Qv;
0 s9 R; M6 w* U* l" Ks(k+1)=v;
4 R* Y9 K. f+ ]& v4 y+ X8 r9 Ak=k+1;
( V2 _2 T! o8 B( E* Ju=s(k);
/ M- [) D4 l: u& j  G& V7 cend
l
1 X- `& T$ C7 x) Az

(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;
! K" U5 q& H3 j. ~: ninf 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;
# j$ a; h' u( x8 O! B8 Y8 _- finf 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];
& x- \0 w+ ~" g2 L' u2 `[D,R]=floyd(a)
floyd.m文件源程序：
function[D,R]=floyd(a)
n=size(a,1);
D=a
4 x/ a" H3 M2 M- Ufor i=1:n
    for j=1:n
        R(i,j)=j;
    end
end
R
9 [! p4 s# V% e; V0 E2 Yfor k=1:n
    for i=1:n
0 m1 ?! j: s3 A# T! O7 C8 D3 S        for j=1:n
( K8 P- O2 h7 }+ f2 p            if D(i,k)+D(k,j)<D(i,j)
' Q* M$ D& J7 n               D(i,j)=D(i,k)+D(k,j);
               R(i,j)=R(i,k);
! L. N$ K" ~8 U" B# K: ]  S6 }           end
       end
6 }% A6 w$ y$ }: c3 g& L6 R. ?   end
" L+ x) H3 g& r   k
9 o) n9 |' X* h' `5 \; j4 f/ g! b, q   D
   R
  P* c; B2 M, ^; f- i6 v3 N$ Hend
) C9 g0 E! _8 }& I$ q9 u五．结果分析
(1)Dijkstra算法
7 ?+ {- K6 g% t) l运行结果：
l = 0   1200   1212   1402   1413   1422   1617   1618   1822   1812
z =1     1     2       2     3       4     6      5      10      8
0 k$ @" \. F- L2 S
结果分析：
9 l& v" T, W6 u( x2 T0 h通过运行结果： 到其他顶点的最短路的权 ，可看出，
到 (即 到 )的最短距离为1812(km)；
到 (即 到 )的最短距离为1618(km)；
- k, T& l( V7 Z1 G" r+ g- G
到 的最短路径为：V1→V2→V3→V5→V8→V10；
到 的最短路径为：V1→V2→V3→V5→V8。

(2) Floyd算法
运行结果：
: x5 Y8 v2 @3 n; Z' _D =
     0  1200  1212  1402  1413  1422  1617  1618  1822  1812
$ x7 c) n) ^9 j5 ?5 f% `3 \  q6 B  1200     0    12   202   213   222   417   418   622   612
' O/ I; c) x+ a) l; y* x6 {. T  1212    12     0   214   201   211   406   406   610   600
  1402   202   214     0    30    20   215   220   424   414
& p2 S5 ?. K  @5 Z5 ]) B4 L' b  1413   213   201    30     0    10   205   205   409   399
- @9 `2 k" }% T7 d" n: H  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
1 v7 c$ q" u, S; H6 L) P$ F: v  1822   622   610   424   409   404   209   204     0    10
- G: e4 |4 X2 C2 k  1812   612   600   414   399   394   199   194    10     0
" y: F" y% n* m: g8 ~( V
0 A7 G/ C3 L- l' ]3 E( a5 SR =
2 l' z. b7 l" ~. ~3 ]/ |8 n, 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
- M$ A2 M; ?3 ^7 N" A- j& X, J0 D   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
  n- z  y( J# U6 j# `   8   8   8   8   8   8   8   8   9  10
# e3 G  d) x! D: p. ]. B1 Q结果分析：
通过运行结果：可看出，
8 G2 f7 k) X$ f: U 到 (即 到 )的最短距离为1812(km)；
到 的最短路径为：V1→V2→V3→V5→V8→V10；
到 (即 到 )的最短距离为1618(km)；
/ h( [, y# m2 m7 N* B1 P 到 的最短路径为：V1→V2→V3→V5→V8。

7 [! k) ~4 r( S/ S' p) x
4 h  ?4 P) \6 D6 T: P0 z& S& X0 Y8 \

1430644259

66666666666666666666666666666