数学建模社区-数学中国
标题:
最短路问题
[打印本页]
作者:
2395960434
时间:
2018-6-6 10:52
标题:
最短路问题
最短路问题及其算法
% Y/ H8 R8 e5 R7 t" ]& z- Q' @( ]
一.实验目的：
1 Q+ C6 T% B& H
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；
% L0 x- d( ~- C9 e8 X: n
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
- O3 R, D' q; K8 Y3 u8 X
二.实验内容：
5 }/ ]& B( X4 K* G* x
要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.
/ O! R A2 Y- h0 ^ b; H$ W
为方便计，1km主管道钢管称为1单位钢管.
9 h: U5 \. h/ X ^
一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元，如下表：
3 X9 i! F( ?5 F6 E
2 d8 s; v7 M' W/ _* x7 n: I
1 2 3 4 5 6 7
# r G( o) j; O: Y8 [% V- \6 j
' n# I% h; f6 f
800 800 1000 2000 2000 2000 3000
2 e! ]0 ~6 a7 U6 m, r
, F+ W7 v o; J3 ]; m
160 155 155 160 155 150 160
, U1 d; H' k1 g
C0 W4 i0 r/ H3 Y. L0 y8 G+ N
1单位钢管的铁路运价如下表：
6 i- T2 ~" `/ R' A9 w- W/ K
里程（km） 300
& [# C3 D9 G' J# g( m3 k2 S
301-350 351-400 401-450 451-500
) K3 `: ^: J( T: R3 }8 M1 O3 @
运价（万元） 20 23 26 29 32
' N" w/ _3 Z3 [ ^/ v% q
里程（km） 501-600 601-700 701-800 801-900 901-1000
! R5 a& I) I" p g# L8 X
运价（万元） 37 44 50 55 60
9 K7 P. }* \1 {- b4 M- j5 {
1000km以上每增加1至100km运价增加5万元.
: y1 ~; J0 p) p/ \) H, ^' V
公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.
+ A0 P* X* C6 l8 H+ i
假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为155万元.
) O8 F; G. Q1 \9 K, R
. o/ M( _4 L4 R7 l
试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划，使总费用最小.
/ k/ _! H4 c7 m- u) ]
三. 模型建立
0 P( `! p1 n3 s, E0 U
设 为 ,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形 ：
6 E8 b2 p6 I6 L- v. j7 m" K
9 q7 f% ]7 @. r# Q+ z
利用Dijkstra算法和Floyd算法：求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离，即为 到 和 的最短距离
5 p! t$ F! X7 w7 X
# I9 j# X8 d) K/ g/ N/ c2 Z
解：先写出带权邻接矩阵：
/ V( h4 M+ K9 Q6 M2 f
3 |+ i3 m% W( e' u. N
后分别用Dijkstra算法和Floyd算法步骤，求出 到 和 的最短路的权 以及 的父亲点标记 .
2 j! m. |1 ^, O" F; ^9 {
四. 模型求解（含经调试后正确的源程序）
8 a" N# ]: m, C6 ~. U- t
(1) Dijkstra算法
5 w. [# a! E) {2 g5 O& {
road1.m文件源程序：
% |0 R0 V8 E1 M, l/ K8 J
w=[0 1200 inf inf inf inf inf inf inf inf;
! R" V; m% h5 f; r. \
1200 0 12 202 inf inf inf inf inf inf;
* e6 J0 b3 U) {
inf 12 0 inf 201 inf inf inf inf inf;
- V, L, S" \! Q6 u: n @( f
inf 202 inf 0 31 20 inf inf inf inf;
2 R# e. K0 ]$ K* z; }8 K1 h
inf inf 201 31 0 10 inf 205 inf inf;
$ G1 g: o5 N3 z6 U. N1 t5 D& ?
inf inf inf 20 10 0 195 inf inf inf;
+ q! h' r2 `& a/ P
inf inf inf inf inf 195 0 5 306 inf;
8 F1 _ k3 V) e" s/ M" S
inf inf inf inf 205 inf 5 0 inf 194;
/ S8 [+ ~5 J" k, P$ u7 }- }
inf inf inf inf inf inf 306 inf 0 10;
$ h5 Q$ x% |$ z+ w# ~5 n
inf inf inf inf inf inf inf 194 10 0];
5 a- Z, {3 U6 t) x* O3 ^
n=size(w,1);
" }' M( [( y1 @
w1=w(1,
;
1 ^( L- o# p: U+ @: _
for i=1:n
% X8 {2 h* X t2 {; ^8 g
l(i)=w1(i);
9 k2 r! ]" R" v, Q* Q* g- S
z(i)=1;
/ z4 T0 l3 v0 {; V& A* d) H
end
7 h( D9 a- f7 K4 t( u" a( Q. `
s=[];
3 @5 ~' w, }. u
s(1)=1;
0 u. x2 W1 U/ u
u=s(1);
% ^- S2 U& X2 \: i8 Q$ v/ u2 v! |
k=1;
5 Y* f+ O7 g Y3 x0 v
l;
2 q Y+ n, j0 q+ @: H
z;
! g7 m) n8 x6 z4 M7 T8 u! \
while k<n
$ _3 V& M6 @3 X( r" ?8 }$ ^; K
for i=1:n
% J& C' Z+ S' a: R0 j1 k
for j=1:k
! ]/ g5 j# Q3 k$ u0 j
if i~=s(j)
. d4 g) I% _% o$ X- M% Y- e! s
if l(i)>l(u)+w(u,i);
4 t$ M; L g) j; A
l(i)=l(u)+w(u,i);
' e3 Y* R3 n3 s
z(i)=u;
) Y1 R. j s' Q W+ l, m; p# j
end
/ y* i8 L# E3 _, W( H3 _" k
end
& S, d" Z; x9 m
end
: |5 T' [8 L! k9 k+ I# g
end
7 B+ j" E; B v% M
l;
* f$ g! S' p- S: p9 B6 u2 Y
z;
+ P: L X& r5 m
ll=l;
! L. t+ `. R1 {6 W7 f: M; M$ s
for i=1:n
$ }8 A& d/ d8 o. u8 E1 r8 D/ ]
for j=1:k
8 |( k7 K) r0 V3 ?3 u7 \
if i~=s(j)
: `0 u) v2 [4 j) E& j
ll(i)=ll(i);
2 _' a* | Y, S% J
else
y9 Q/ K% _/ u0 N3 W
ll(i)=inf;
0 P- f0 G+ B$ c, m. m
end
. X, u. z& _. S5 [4 [: ?3 j
end
" e$ h( U* e6 ^% {! G
end
7 y9 ]1 C/ M; w
lv=inf;
) F* t8 k4 G; N) N4 O4 L: F
for i=1:n
" G! A) H* A3 z" g
if ll(i)<lv
/ G- L! E, L" }9 ]
lv=ll(i);
) i2 X1 O4 H6 ~6 Q. @ y! W
v=i;
1 q3 u5 Z" W( h, L4 F5 L
end
( ^* x6 r) o; B
end
/ p4 X7 Y: S7 c$ C
lv;
2 _4 R, s# a- V5 e; U' K
v;
' v) V9 Y- o# L3 t8 }7 v0 J
s(k+1)=v;
8 ~' w0 f$ C# k7 h; r
k=k+1;
2 d- a- i6 B. s( O! g: h6 Y
u=s(k);
1 |, b6 E% v* x
end
" e! p/ G" p$ l7 ~8 J, g+ e
l
6 O& O# y! A, M- h. O% s" p: {# D
z
2 M: ?4 G# y4 F. f7 m4 ?
) k1 X( _1 s1 g; w5 ?
(2) Floyd算法
8 o# ]( i8 K' z# j I5 w
road2.m文件源程序：
$ s8 V+ T0 [/ R& r: e
a=[0 1200 inf inf inf inf inf inf inf inf;
0 R# L7 L( z* H [, T/ d+ O* Y
1200 0 12 202 inf inf inf inf inf inf;
k! T7 J$ X A; }' w1 t' Y
inf 12 0 inf 201 inf inf inf inf inf;
% @6 O4 v" q! G' f
inf 202 inf 0 31 20 inf inf inf inf;
% b$ i& k* g+ r; o4 f* J& u
inf inf 201 31 0 10 inf 205 inf inf;
# |/ i- E# J" C; q. r% z4 I* ^
inf inf inf 20 10 0 195 inf inf inf;
1 v1 u' Z6 F6 p/ a! F4 _3 @
inf inf inf inf inf 195 0 5 306 inf;
4 G$ m' K6 E2 E. o/ Y" z: V
inf inf inf inf 205 inf 5 0 inf 194;
) }) B! L1 s# E8 }, a& u
inf inf inf inf inf inf 306 inf 0 10;
6 f2 `7 {+ h9 r0 I8 |- b. B) t
inf inf inf inf inf inf inf 194 10 0];
7 I6 ? _0 v8 J! X
[D,R]=floyd(a)
0 k- p0 G$ |0 i" d! c. T0 k! ?
floyd.m文件源程序：
* ?6 h B' w+ e7 k1 \$ c
function[D,R]=floyd(a)
" B; `" Q7 V& w' ?. v
n=size(a,1);
( ?/ z4 B' Z8 g2 d* c# o+ |2 u
D=a
; b2 R e' w" D3 [8 x: ~
for i=1:n
. p3 k# \+ k$ a! I& {7 T3 E
for j=1:n
& _% J0 @" P/ ?1 v: V/ l6 }5 p
R(i,j)=j;
* y# o- [* v% d* e* L) Y
end
* g. ?& Q" e( F) p9 Q
end
9 v2 k# s; `/ p% D8 Y
R
t+ ?9 y0 h3 U4 M: C
for k=1:n
a9 N* t+ f5 M3 q, p) ]
for i=1:n
7 d/ a8 V) H9 g& B
for j=1:n
E' f, h6 r6 m1 q9 M7 J6 z/ A" e
if D(i,k)+D(k,j)<D(i,j)
# ~$ b& R( @6 t9 L* [9 } h
D(i,j)=D(i,k)+D(k,j);
9 y; b0 |9 R1 _
R(i,j)=R(i,k);
) n% P: |, E' m) q# Z1 V! [
end
& G- F" B! o9 K* j- X- L) v, O& S! P
end
3 Y# y+ W9 Y2 v3 o. k( M4 l
end
$ a. f% l& B* p2 C' j2 u! I7 y
k
- q" t: b; c3 D
D
% V" H9 ^- l0 r+ `/ R) A" m
R
& `% Y8 K7 ^2 L
end
$ h1 _! D! o2 j% z5 ]; U+ o: v
五．结果分析
- c( ~& m7 Z( D
(1)Dijkstra算法
0 M/ n5 m6 F! g: {1 M
运行结果：
5 f5 i" ?: U- k, X! E
l = 0 1200 1212 1402 1413 1422 1617 1618 1822 1812
6 g; T* J+ t& T/ `
z =1 1 2 2 3 4 6 5 10 8
9 d) r+ U: I8 e. j Q9 y+ j9 K
3 @; i/ k! K+ @
结果分析：
% T8 J1 J( i; {$ ?. r0 `, ^; z
通过运行结果： 到其他顶点的最短路的权 ，可看出，
) e' H+ k: S6 r: a+ Z
到 (即 到 )的最短距离为1812(km)；
" C' X- n4 m$ P( K
到 (即 到 )的最短距离为1618(km)；
6 [4 Y9 N' b3 X' W3 l
4 N5 K0 w6 \- S/ s( x1 q
到 的最短路径为：V1→V2→V3→V5→V8→V10；
& K3 u. F1 F4 `: M, D
到 的最短路径为：V1→V2→V3→V5→V8。
+ W* k. H; f0 w: q+ ?) X8 S
* W* N/ _, M9 H6 ^/ K; m& \
(2) Floyd算法
/ g4 s/ R8 Y$ s6 N' R0 _
运行结果：
) b, e) C$ g( U# z. h, `/ j- g7 y7 M
D =
4 I' p. g: R" t" ^, l
0 1200 1212 1402 1413 1422 1617 1618 1822 1812
# M- \# E( o7 r; Y! ^, c u" @
1200 0 12 202 213 222 417 418 622 612
: v7 a1 l2 j) h; D% E \
1212 12 0 214 201 211 406 406 610 600
5 q' T- c+ D5 {+ q3 y
1402 202 214 0 30 20 215 220 424 414
3 |) F8 Z: F' O* F* [8 S
1413 213 201 30 0 10 205 205 409 399
8 ?' x- x0 {# h
1422 222 211 20 10 0 195 200 404 394
/ h3 \+ v8 @$ Y: l
1617 417 406 215 205 195 0 5 209 199
8 }8 h7 B0 I8 `1 G9 ~9 P
1618 418 406 220 205 200 5 0 204 194
5 D1 Y2 e5 O8 \
1822 622 610 424 409 404 209 204 0 10
% n* h8 ~) M) Y. Z
1812 612 600 414 399 394 199 194 10 0
1 U/ H3 u* ]- N7 c
( k' h( B, \. f6 b( A
R =
$ M0 r0 M: D2 g6 C" O, s3 P
1 2 2 2 2 2 2 2 2 2
- c9 S+ q( `* i2 D" {
1 2 3 4 3 4 4 3 3 3
4 H& x- I3 X# B$ _( T
2 2 3 2 5 5 5 5 5 5
- L% B1 w4 G& u) @6 o) L9 G# z
2 2 2 4 6 6 6 6 6 6
3 n d# q* @ I, v
3 3 3 6 5 6 6 8 8 8
' f1 `; b1 d, Q; g5 K/ G( C6 N
4 4 5 4 5 6 7 7 7 7
* z. b0 v O) S3 z6 m3 t
6 6 6 6 6 6 7 8 8 8
! S, ]6 y$ f9 P) e) s' Y/ e! _
5 5 5 7 5 7 7 8 10 10
$ Z9 b1 R. |: i3 o
10 10 10 10 10 10 10 10 9 10
: Z& E- `+ x% X9 X* R
8 8 8 8 8 8 8 8 9 10
8 C m' D) x8 u( y
结果分析：
8 b X* G8 `4 ?: [, f5 h& M
通过运行结果：可看出，
- P" e6 n8 \! G7 @
到 (即 到 )的最短距离为1812(km)；
9 x/ n# H* \6 v& [& t
到 的最短路径为：V1→V2→V3→V5→V8→V10；
9 \2 @/ h5 g5 B5 V; }, I1 v& W& m% x
到 (即 到 )的最短距离为1618(km)；
# V7 y- v) @* {3 J; ~
到 的最短路径为：V1→V2→V3→V5→V8。
7 K; l; ?; T; e$ H8 y3 o; P2 F
* h- [, _2 g; l3 }) E
: Z4 Z. @. k1 ^% Y, f9 M
作者:
1430644259
时间:
2018-8-9 14:50
66666666666666666666666666666
4 J3 [' l3 T, ?+ `" m, @
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
;