数学建模社区-数学中国
标题:
最短路问题
[打印本页]
作者:
2395960434
时间:
2018-6-6 10:52
标题:
最短路问题
最短路问题及其算法
3 d. [. C0 g% t
一.实验目的：
- d& B8 Y# C/ N* v2 }; x; V+ ]7 @! l+ O4 W
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；
% T0 n C2 k+ W8 n
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
8 ]/ ?9 ~) O+ t6 _ @
二.实验内容：
7 R" L7 ]5 ?5 x7 v# l, w9 n: y/ |
要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.
4 F3 U5 }4 x6 [+ A' _& }9 A. @, ?/ R
为方便计，1km主管道钢管称为1单位钢管.
- Y) N* `( m; U6 C1 B
一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元，如下表：
" y! E$ Y/ Z2 P6 g
1 s8 _9 h I$ e
1 2 3 4 5 6 7
/ d8 r! q: d6 o
) T5 C# b, S0 B5 |) C
800 800 1000 2000 2000 2000 3000
9 _( O+ y4 b5 R' w+ d6 I( O
# k* ^3 y* S% x! F
160 155 155 160 155 150 160
5 f% g' U1 y1 Z+ [( U: @6 p: v
9 P4 H: f4 t9 O% c! _
1单位钢管的铁路运价如下表：
2 e( }3 t. E4 ?3 Y1 _+ s% j" y, L. P, b4 [
里程（km） 300
6 T+ \5 u& O# H
301-350 351-400 401-450 451-500
) [1 _2 G: T$ S0 d" y% J- Z
运价（万元） 20 23 26 29 32
, r, P: X4 h: \# m
里程（km） 501-600 601-700 701-800 801-900 901-1000
3 F+ h5 l! S- A) R/ S
运价（万元） 37 44 50 55 60
* n, h8 L5 M$ g7 B! o) J
1000km以上每增加1至100km运价增加5万元.
5 I& J2 ^( |" L4 D' q
公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.
/ q6 C3 u- |+ I% [. R) o6 N
假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为155万元.
, }8 E% ~* `1 i; {' e" h
$ A/ X3 s3 H8 c n$ O: o
试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划，使总费用最小.
5 I1 |( Z: X. ]! n! A+ r' |
三. 模型建立
1 E" V. X( w @9 d0 w
设 为 ,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形 ：
) ?) m' t# c |0 G: o8 L: U b, C
2 B4 L# ?1 ~; l( \
利用Dijkstra算法和Floyd算法：求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离，即为 到 和 的最短距离
- t5 {: W1 q w1 l1 R" |9 W# ^
* G4 c; ]( z$ U L6 z
解：先写出带权邻接矩阵：
3 ?5 b* a6 U6 a7 S0 Z; n( }' j
+ \% A8 \* |" P2 u8 w% f' c" U) O
后分别用Dijkstra算法和Floyd算法步骤，求出 到 和 的最短路的权 以及 的父亲点标记 .
: o0 a. M, }7 D, T6 h6 U& V
四. 模型求解（含经调试后正确的源程序）
, r+ t' [' I3 e) h G$ Z
(1) Dijkstra算法
3 r& i7 B5 I& L% I. j1 u: T) a# i$ r ~
road1.m文件源程序：
8 n5 u1 ~* Y. y* ?' Y" P; n
w=[0 1200 inf inf inf inf inf inf inf inf;
9 _: y' U+ j0 |1 x) V
1200 0 12 202 inf inf inf inf inf inf;
0 x1 j! A. g9 W& y
inf 12 0 inf 201 inf inf inf inf inf;
4 A( v+ x- P4 B9 G
inf 202 inf 0 31 20 inf inf inf inf;
0 ^# O0 r' B; q
inf inf 201 31 0 10 inf 205 inf inf;
+ N6 v- W& p! ?. @: Y+ ?
inf inf inf 20 10 0 195 inf inf inf;
. Q6 O# O% Y: p+ P
inf inf inf inf inf 195 0 5 306 inf;
! A. w! `8 G/ j, g( v) W, R# s
inf inf inf inf 205 inf 5 0 inf 194;
" l7 w1 `+ {! E* f% Y! p1 a! X* X
inf inf inf inf inf inf 306 inf 0 10;
- `# z- L0 q* `8 z
inf inf inf inf inf inf inf 194 10 0];
Z2 j4 `) a% h/ }0 x4 L5 M4 {
n=size(w,1);
% t$ b3 U7 D* {- s+ H& _* T
w1=w(1,
;
6 D' j6 `. B/ d# ?$ }
for i=1:n
7 T( p, r4 u6 ?: w
l(i)=w1(i);
4 G2 g0 l* Y% J9 T+ f+ Q0 S
z(i)=1;
& k- k, A( G% |0 U$ h
end
% w k% D* g% x
s=[];
, P. e0 a8 @8 O2 v. n
s(1)=1;
1 R$ ^. M$ W$ t+ A5 I
u=s(1);
& s& N/ s( U' T; _
k=1;
- h8 j. R P6 A; W9 A, T, E
l;
6 p. U' O5 R" L; \2 K
z;
4 p4 d5 E# H$ B6 E: C+ j9 Q
while k<n
* L A4 `5 S4 M ?
for i=1:n
, k5 ?- ?( h- C0 O
for j=1:k
1 I& s$ `# I, D. C2 i0 C/ |5 g
if i~=s(j)
9 f% o. d% X# Y B2 f1 P
if l(i)>l(u)+w(u,i);
' ]( M" \( z2 B! `# e
l(i)=l(u)+w(u,i);
* S% d5 s. |) T( Y6 z9 ^: ~( C
z(i)=u;
3 p4 B1 z; Z e2 q5 T% B
end
* y7 T* {2 B; ]$ O1 B" T: J
end
2 i! o) f! G' d+ J
end
2 m$ ]& a) I( {
end
9 e) ~6 N0 u9 E5 \) ?0 k
l;
6 D3 r$ _# y/ f* w
z;
' b' X G( U/ @) ]7 }/ u! U( [" [0 G5 h
ll=l;
$ F1 C+ k6 a# a) B/ \
for i=1:n
5 | p a0 P7 W
for j=1:k
+ n3 J+ v. }. Y
if i~=s(j)
' v: G5 A: }$ N1 I( J$ K
ll(i)=ll(i);
5 X& b- E3 D3 Q: f. i" Y5 n; I
else
/ ]4 ^, W: e& e% s8 ]
ll(i)=inf;
/ D: }9 {7 Z; U' z7 {; o
end
1 j% P( V' z6 D- Q
end
- A- y0 P' O. J/ i" z, f
end
. k2 e6 O+ c& x' a
lv=inf;
( j1 O4 }+ T/ [0 _: c q
for i=1:n
+ W( I2 d- _9 O u% } Z
if ll(i)<lv
7 N5 ]& Z1 j, ?7 S4 {
lv=ll(i);
8 n2 }. ?+ q* Y/ @5 C
v=i;
8 @" N( ^2 s5 k% A# Q% m
end
/ e+ d% S' s) F. U: @8 U( S' U
end
2 k) ?, j& Q7 N' T4 d; v" r' ]
lv;
% S$ M0 d* p, P& x* \
v;
. D& j4 ^2 U' Q( x
s(k+1)=v;
7 p# m h7 o7 a3 U8 n3 Q% u- f* t L
k=k+1;
; c( m; |" ^# D9 @
u=s(k);
# H: l0 g" i' F
end
/ p9 j9 n( m( ~
l
; C- s3 N: ?6 E0 T
z
+ ?9 Q* P$ B o5 y8 f
# _9 J, q2 S9 N; m' C9 F6 J# m
(2) Floyd算法
" z$ v5 M6 D6 i- |. Q" }* Q, f# L
road2.m文件源程序：
+ C' Q; a: {" T7 A
a=[0 1200 inf inf inf inf inf inf inf inf;
5 g0 d* H1 q5 G& R- `# b+ c/ ^$ |
1200 0 12 202 inf inf inf inf inf inf;
/ k( c! Z/ K5 C# `6 V
inf 12 0 inf 201 inf inf inf inf inf;
0 @" D9 B" X2 i& U5 h- m5 u
inf 202 inf 0 31 20 inf inf inf inf;
# c- T( m: S- O& O% N. X
inf inf 201 31 0 10 inf 205 inf inf;
7 _2 e. B3 M8 Y$ [% v
inf inf inf 20 10 0 195 inf inf inf;
Q: [$ a2 h: ^8 H
inf inf inf inf inf 195 0 5 306 inf;
6 _, B& Q# j. r* a
inf inf inf inf 205 inf 5 0 inf 194;
; R, Z( H5 |- v1 D7 n% ^
inf inf inf inf inf inf 306 inf 0 10;
: z) W0 e6 ]2 f# }
inf inf inf inf inf inf inf 194 10 0];
* C" y2 ]# V1 m/ h5 Q
[D,R]=floyd(a)
9 K) [3 T) M* e* ]- ~1 l
floyd.m文件源程序：
, Q0 h8 {$ _8 ?3 k. ?! h% \
function[D,R]=floyd(a)
, d7 G. ]5 P3 K. H( o
n=size(a,1);
. `6 M0 F5 P+ u2 @. Y, }: i, i
D=a
4 u( {/ j1 |4 @/ j( d ^8 i- s; q
for i=1:n
+ F$ u( S" P# |; K. i7 m
for j=1:n
$ h& w' L$ L6 ?( G: p
R(i,j)=j;
! o6 y$ @$ i7 s- v
end
/ _: g% }: m% e
end
3 _4 j7 ?+ m1 P. V5 W' F# x8 j
R
- h! j _' B0 b) j* a0 C/ x
for k=1:n
l) b9 j& r+ |4 u, `
for i=1:n
( ~0 ^/ g; E8 h2 Q
for j=1:n
7 q# Y; f: N1 ~* ?
if D(i,k)+D(k,j)<D(i,j)
4 p; P( j9 Y3 d/ |4 _
D(i,j)=D(i,k)+D(k,j);
( v: O# G, _2 W0 E5 ~
R(i,j)=R(i,k);
4 c3 J) H# h5 h! N
end
; @% D( T/ W) h& W
end
' K' O. b0 W, A% H- f- Q# N
end
2 p+ C' t: z# q( B
k
% m3 {" H3 K: z/ b
D
. y. Z+ `: P* S( @$ P
R
0 p- y' T/ H. {5 G. H9 H
end
7 N }* F R: {) C8 k5 g* G
五．结果分析
- z; J5 a' v) R# y9 A
(1)Dijkstra算法
, K6 }) h! U R; v. j) y' y0 z) E
运行结果：
2 o; \$ p" O& W3 |
l = 0 1200 1212 1402 1413 1422 1617 1618 1822 1812
) _3 X% }$ }4 q! P! p4 l' l. O3 p
z =1 1 2 2 3 4 6 5 10 8
$ F5 I6 g- |( e% q0 u7 m
& ~0 O: W6 ]+ R. g. x5 r
结果分析：
3 Y4 o- U2 [8 H7 d
通过运行结果： 到其他顶点的最短路的权 ，可看出，
* @( l9 X7 W# U; L, P2 o5 C4 c
到 (即 到 )的最短距离为1812(km)；
2 E+ L+ g+ V4 u, O# J- V: k
到 (即 到 )的最短距离为1618(km)；
) l, t# b! Z& e% \7 E- S" F n
6 u8 B+ ~& w) w! n- H6 E
到 的最短路径为：V1→V2→V3→V5→V8→V10；
3 n, [5 s' k6 c. g3 c8 v
到 的最短路径为：V1→V2→V3→V5→V8。
% P6 j: Q8 C6 n. N
, }' Q5 F" n! j# m4 n: ~
(2) Floyd算法
3 o# ^; i% F6 z; Q z( G# W
运行结果：
3 ~: O5 Z2 n6 |2 G7 ]/ U$ \& v7 a
D =
- F6 R4 O6 |9 M; d* j
0 1200 1212 1402 1413 1422 1617 1618 1822 1812
" E. R1 Y6 t( i: @4 q ^3 q
1200 0 12 202 213 222 417 418 622 612
4 ^" E- Q& q8 F7 E4 Z: ]7 q
1212 12 0 214 201 211 406 406 610 600
; r3 Z A7 c6 m: t
1402 202 214 0 30 20 215 220 424 414
& u+ m# O2 c' | x, Z! }
1413 213 201 30 0 10 205 205 409 399
% r9 S6 U1 r3 W( L" @6 r7 Z
1422 222 211 20 10 0 195 200 404 394
: P- \! w |4 G: U/ |/ O9 }
1617 417 406 215 205 195 0 5 209 199
7 j7 I2 b3 C" J
1618 418 406 220 205 200 5 0 204 194
* W, i1 C: L1 O& o( V- h( q
1822 622 610 424 409 404 209 204 0 10
- t( k7 R; H% J3 L
1812 612 600 414 399 394 199 194 10 0
6 G3 X7 O* M( @; B9 H" t% _6 P
- M0 k2 o; O4 U# k
R =
$ v+ ?5 H, w4 K7 ?) u/ _3 `+ z& d
1 2 2 2 2 2 2 2 2 2
2 A$ {% j) `0 b
1 2 3 4 3 4 4 3 3 3
A# Z& x i+ Y) J( H' G
2 2 3 2 5 5 5 5 5 5
: u X' e' W% R$ }: N$ M4 i
2 2 2 4 6 6 6 6 6 6
2 h& c' V/ [# h, y4 s: }+ f/ I
3 3 3 6 5 6 6 8 8 8
/ m [' ~4 n3 s. h3 O9 t9 H
4 4 5 4 5 6 7 7 7 7
/ H5 r7 Q) l& b; C
6 6 6 6 6 6 7 8 8 8
. f& c. G1 o: e4 Y
5 5 5 7 5 7 7 8 10 10
3 B% R" r- C0 e6 }
10 10 10 10 10 10 10 10 9 10
- M5 ~* L5 M* K- n3 g
8 8 8 8 8 8 8 8 9 10
8 Q. p+ d8 m2 U- T8 W
结果分析：
$ @: `8 [# B* y2 L
通过运行结果：可看出，
0 `) B& d( d; E' s$ d; Q7 ]
到 (即 到 )的最短距离为1812(km)；
( @" c' F+ l% F- D; f: E; q
到 的最短路径为：V1→V2→V3→V5→V8→V10；
; Y6 x; i( v& k& o
到 (即 到 )的最短距离为1618(km)；
$ j6 N( D4 N$ g! F
到 的最短路径为：V1→V2→V3→V5→V8。
7 w6 q% {- }3 N+ n7 D0 _
+ [- F7 ]* \! l4 l, q4 u# L9 q# v
! s/ l+ R; v) M4 K8 T0 {6 Q4 c
作者:
1430644259
时间:
2018-8-9 14:50
66666666666666666666666666666
, O6 x" F, B$ A
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
;