最短路问题

2395960434

最短路问题及其算法
一.实验目的：
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；
, }4 A% h7 }( p8 s2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
二.实验内容：
7 G- v: W3 E+ b+ n; H+ y) q要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.
为方便计，1km主管道钢管称为1单位钢管.
一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元，如下表：

1        2        3        4        5        6        7
# ~' N  K5 v9 z) ^, L8 I; I* c
) D1 _: Y( ?! X9 L800        800        1000        2000        2000        2000        3000

160        155        155        160        155        150        160

9 E! l3 x& M3 j% h, ]. b# t; u1单位钢管的铁路运价如下表：
) U$ s1 V3 Q' I) A5 _% u里程（km）          300
# [! d3 S1 J2 g) N2 R; K5 W4 D301-350        351-400        401-450        451-500
运价（万元）        20          23          26          29          32
0 Z. A, q" l) |) D4 ^7 @里程（km）        501-600        601-700        701-800        801-900        901-1000
/ r4 s: k% {" X/ N; t; W) Y6 _运价（万元）          37          44          50          55          60
  Y1 u" b' n+ D! m. y1000km以上每增加1至100km运价增加5万元.
' @% P: `, n/ o8 E+ a公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.
0 N0 f4 [8 A8 O4 E. f$ y  X假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为155万元.
4 s1 ?1 v% h9 h4 O
2 M. [2 }+ r/ q" y试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划，使总费用最小.
三. 模型建立
设 为 ,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形 ：
# M# k9 ]' @+ E. @, H- D
: L8 {+ v8 p& B# L. c利用Dijkstra算法和Floyd算法：求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离，即为 到 和 的最短距离
8 V( O+ C. E. N
# a" O& j4 \. O8 v+ S+ D/ o% Y解：先写出带权邻接矩阵：

" T/ _/ Q- v$ I( f后分别用Dijkstra算法和Floyd算法步骤，求出 到 和 的最短路的权 以及 的父亲点标记 .
四. 模型求解（含经调试后正确的源程序）
(1) Dijkstra算法
road1.m文件源程序：
w=[0 1200 inf inf inf inf inf inf inf inf;
, x5 x& y, Q" m9 ?6 i1200 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;
% q7 D8 ?" Q! ~% e! R- linf inf 201 31 0 10 inf 205 inf inf;
  G8 h1 k' G7 r2 Pinf 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;
0 A2 O2 k8 y8 k$ z& N# vinf inf inf inf inf inf inf 194 10 0];
n=size(w,1);
3 Q! o9 k" G4 mw1=w(1,;
for i=1:n
1 O% h8 o: E0 T& W7 ]    l(i)=w1(i);
    z(i)=1;
end
s=[];
s(1)=1;
! N- J5 Z1 T. {* ~% |% d1 Ou=s(1);
  o7 _- \2 Y& g; V4 xk=1;
0 Y8 `/ W. k8 y5 S. G% J; V- }l;
- ~0 C: ]9 s8 c9 Z9 D3 ~5 T2 f7 zz;
while k<n
    for i=1:n
    for j=1:k
       if i~=s(j)
2 @+ D3 K" d/ ?0 t          if l(i)>l(u)+w(u,i);
7 g$ U& ^% Y# ?/ t0 `$ q0 y$ m( j. a             l(i)=l(u)+w(u,i);
! b9 @3 P1 L' W             z(i)=u;
' I6 a6 S7 ~7 c- `& l$ {9 n- f4 |  W         end
4 o% O1 @8 Z0 c- W" x     end
end
, g& g0 C& C- E. r" D6 dend
l;
z;
ll=l;
for i=1:n
for j=1:k
& {- W& u; @& K/ n& N$ U    if i~=s(j)
       ll(i)=ll(i);
   else
' V" A' W; p- {2 k$ ]" I       ll(i)=inf;
   end
end
$ U! r$ j: b$ m$ \end
lv=inf;
for i=1:n
& H6 ^7 s* e0 }% O% l: s/ `    if ll(i)<lv
       lv=ll(i);
       v=i;
2 B7 ?6 v& ?! w( x   end
8 Q% o( p! q3 p' n# `end
7 `; z4 a: m! {, Clv;
v;
# v0 S5 l: R) m6 U( ?+ ~# {s(k+1)=v;
k=k+1;
$ {' k' T! _! Xu=s(k);
end
l
; J& U, x% B. G& [z
" |) `5 {9 S2 c' ~, q  f
(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;
) |7 x9 k3 F+ xinf 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;
2 v+ k( u" g+ r/ a7 Z- V; linf 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;
% [$ H! P' V9 J: C) |inf inf inf inf inf inf 306 inf 0 10;
3 v* b2 f; E( Z& ~3 Yinf inf inf inf inf inf inf 194 10 0];
[D,R]=floyd(a)
5 h3 q" ?+ y" e7 T9 k9 V( mfloyd.m文件源程序：
. Y3 a7 k, |) N. G# ?function[D,R]=floyd(a)
n=size(a,1);
& V( L; h: K7 f. @0 K/ ^6 U' F6 R3 kD=a
for i=1:n
    for j=1:n
        R(i,j)=j;
) F" z  B4 Y5 h* @    end
end
R
4 Z! f1 r% ^" X  z2 {$ E( i$ Kfor 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);
. Z- [& k/ h1 p  M, R( z, C6 E( _' x               R(i,j)=R(i,k);
           end
+ E4 W( e3 T, M3 J       end
   end
   k
5 T' y) T# U. U- q7 |' q/ T9 Y   D
   R
1 N& F: u5 l0 x2 Rend
6 r& p% L  c) |( Y9 u- }, h. i' X五．结果分析
(1)Dijkstra算法
" N% @# V2 t+ e3 q5 [; d运行结果：
. b  s, i1 A6 y) |5 K* k) xl = 0   1200   1212   1402   1413   1422   1617   1618   1822   1812
2 ?+ \5 h% q) j5 k3 Nz =1     1     2       2     3       4     6      5      10      8
* o) d: s2 N5 V) E6 `2 B' k( s
结果分析：
通过运行结果： 到其他顶点的最短路的权 ，可看出，
到 (即 到 )的最短距离为1812(km)；
到 (即 到 )的最短距离为1618(km)；

到 的最短路径为：V1→V2→V3→V5→V8→V10；
, M, X- @% B5 r) e9 K  x. Z6 f 到 的最短路径为：V1→V2→V3→V5→V8。

3 [. e4 r, r$ h+ ~; D(2) Floyd算法
  E. _. r8 W; r, _& b运行结果：
D =
/ Z2 d3 S% J: {     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
' U! B4 k0 Y) t8 v' V  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
2 w3 M9 m9 U9 y! v  1618   418   406   220   205   200     5     0   204   194
  1822   622   610   424   409   404   209   204     0    10
" r+ Q2 Y, r' G4 d  1812   612   600   414   399   394   199   194    10     0
1 S% ^+ F% Z# r+ I! v* Z
R =
   1   2   2   2   2   2   2   2   2   2
6 N  n% Y5 r( G( X% q   1   2   3   4   3   4   4   3   3   3
   2   2   3   2   5   5   5   5   5   5
3 e3 R& ?# _7 c) g+ I   2   2   2   4   6   6   6   6   6   6
   3   3   3   6   5   6   6   8   8   8
) s2 L2 B, {0 X2 s! B   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 ]" }4 ]: Q1 J5 V5 Y   8   8   8   8   8   8   8   8   9  10
结果分析：
通过运行结果：可看出，
到 (即 到 )的最短距离为1812(km)；
到 的最短路径为：V1→V2→V3→V5→V8→V10；
5 o: F# _0 [6 w, H8 D! P2 G 到 (即 到 )的最短距离为1618(km)；
" W6 `0 ?  X# ?% |; f+ P 到 的最短路径为：V1→V2→V3→V5→V8。
# G7 g' P/ }$ P5 m" m

  A2 g; e7 I- T

1430644259

66666666666666666666666666666