数学建模社区-数学中国
标题:
最短路问题
[打印本页]
作者:
2395960434
时间:
2018-6-6 10:52
标题:
最短路问题
最短路问题及其算法
4 T8 T1 F C0 `' Q* Q; t
一.实验目的：
' t7 e! z! Z/ Z
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；
6 b: e. e' I+ j$ T% f$ k" X! d+ P
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
9 C7 i2 X, N" y
二.实验内容：
0 U8 d6 x: r7 }, H+ N# @: z) ~: f
要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.
7 b* I: o% p8 e3 k0 @+ h0 b
为方便计，1km主管道钢管称为1单位钢管.
8 [% D' x" {( z3 q
一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元，如下表：
, l) ~( e& B8 D& V0 Y9 X: @
! k0 ]4 {+ V2 A& X; Z! j) C
1 2 3 4 5 6 7
$ l' m% P/ R" H: d2 ?3 y3 i! f( V
0 [; N( J4 D( `# f& f7 \5 `- u
800 800 1000 2000 2000 2000 3000
2 ^2 G$ G$ ~) k/ \8 r
# p" Z$ q# f% _
160 155 155 160 155 150 160
6 c$ P# t2 k H0 W
2 C2 |! Q3 { a1 d- r7 t
1单位钢管的铁路运价如下表：
% p) i& L* @! ?6 X/ ~$ T
里程（km） 300
3 e5 I P O+ C2 }
301-350 351-400 401-450 451-500
2 M: e0 q G4 n6 p7 @9 G! A
运价（万元） 20 23 26 29 32
+ f. X( Y1 Y" z
里程（km） 501-600 601-700 701-800 801-900 901-1000
$ r/ ^# r" e- Y4 \
运价（万元） 37 44 50 55 60
2 o$ R- E- Q1 ~6 w2 l( P [& |
1000km以上每增加1至100km运价增加5万元.
. t2 Q- _ L# Q$ j! o
公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.
3 |' H1 }# u3 |2 a* ^( y
假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为155万元.
0 `3 n. H% ]; P5 p' l
8 G6 N( {; _+ M
试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划，使总费用最小.
- F$ w) s4 L. V. i
三. 模型建立
' X0 J3 o q* V6 \4 N: u
设 为 ,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形 ：
y) q4 T2 p+ j! ]. Y
; P$ q7 @1 \. Q3 p$ B
利用Dijkstra算法和Floyd算法：求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离，即为 到 和 的最短距离
2 u! N* R( V1 o+ v* K
1 c k7 a8 U7 q1 A7 `9 q
解：先写出带权邻接矩阵：
( e$ z) `' W7 l$ g* j$ T' J$ [5 M; X
9 g4 V, b; y7 F; n: |, G
后分别用Dijkstra算法和Floyd算法步骤，求出 到 和 的最短路的权 以及 的父亲点标记 .
4 [9 [8 B3 m8 ~9 U( u1 _
四. 模型求解（含经调试后正确的源程序）
1 B% G$ f5 P7 h" E
(1) Dijkstra算法
2 B& t( |2 K& {1 N/ }
road1.m文件源程序：
8 J& r* W5 k: E3 H! n% F& Y' X
w=[0 1200 inf inf inf inf inf inf inf inf;
' e5 ?% ]2 A" m0 w! ?
1200 0 12 202 inf inf inf inf inf inf;
' k5 L! k; n7 ], _: @, c5 }6 v* D8 |
inf 12 0 inf 201 inf inf inf inf inf;
9 ]7 c b9 Z" C# U- v0 R
inf 202 inf 0 31 20 inf inf inf inf;
& z$ y, Q# T3 v0 h% y2 x
inf inf 201 31 0 10 inf 205 inf inf;
0 J8 A6 w: s* D
inf inf inf 20 10 0 195 inf inf inf;
( L9 T0 ?1 ~+ r# K. J' K9 P3 |
inf inf inf inf inf 195 0 5 306 inf;
: \( X* _& J r. [
inf inf inf inf 205 inf 5 0 inf 194;
3 o; L* J4 E4 P- B+ M! B$ z
inf inf inf inf inf inf 306 inf 0 10;
7 K1 [/ `# V/ o6 K) k5 Y$ T
inf inf inf inf inf inf inf 194 10 0];
: O) |# Z1 E) U8 F& P
n=size(w,1);
) v7 }( h9 G1 a+ Q5 g: d/ D- R
w1=w(1,
;
; T0 g f* G5 e8 R
for i=1:n
- k5 i4 J' E3 v# r. U5 }6 a; \+ p$ C
l(i)=w1(i);
; }$ Z+ ?# w P1 ]/ M" T X
z(i)=1;
2 q0 z2 S6 d& A, c
end
$ \) b; k2 W4 s7 r
s=[];
. k- u, E) m' A+ m9 u0 A$ N, P
s(1)=1;
3 z3 f# z. p3 h
u=s(1);
& ?3 L% j, I; \- o! v' @' K
k=1;
* l+ h6 A0 h3 q5 e# e- v4 }! B
l;
6 y! ], q3 v5 h. u( \
z;
( y2 v2 n. t6 T2 @5 S
while k<n
% |9 s. ]* e- ~5 R$ ~3 t9 F
for i=1:n
/ n1 a( ]( Z( t/ r& y. @
for j=1:k
4 C1 d& }4 Z4 M3 X* H' C6 T7 V
if i~=s(j)
+ O. l1 i; L6 [ v0 s
if l(i)>l(u)+w(u,i);
$ Z* F9 u- o: G; k
l(i)=l(u)+w(u,i);
9 m$ D( f' @: Q( P( C1 u
z(i)=u;
) v# ~4 R; p# {: G
end
1 V* m0 c; @1 A2 N& z$ y# J
end
8 y# o1 }4 M1 C% j( x! `
end
$ A: f# K- e0 s: e$ _. f1 q
end
- w, k# O) h3 X; A g. n9 A
l;
0 B1 B" a0 ~+ L0 F" U2 k! {
z;
6 z2 h% y% e+ F8 [
ll=l;
' e2 ~1 F- |# F, F+ o
for i=1:n
3 S" s& `5 N: \0 P" }
for j=1:k
6 o G. ]: r$ `) z2 ?
if i~=s(j)
; c$ Z; l2 h. Q( k4 t# B# q ]. {% d% e
ll(i)=ll(i);
6 ~) b' Z. T7 o5 M8 w5 O/ l
else
* n( d( u/ h1 y- w) Y; y9 Y
ll(i)=inf;
9 J0 x% U! M4 L+ ^9 l) y
end
3 k* W$ L8 ]; K2 V* U# Z+ }! ^
end
* j1 l/ @! K& J/ C" E0 T F! @
end
6 }4 K2 g: E2 d4 f5 b& q, o5 b7 ?! u
lv=inf;
; N" X# e$ C0 A7 L# ?% P
for i=1:n
$ O0 C/ D( n$ k% l9 d1 v
if ll(i)<lv
/ \! L c2 X: N. d2 U
lv=ll(i);
1 j1 M6 _7 Y* | e
v=i;
A4 o. n' ?, |" ] J- x$ ^
end
" ?/ ^) z1 T" c" ?! \
end
% } E& Z0 `0 g6 l
lv;
8 v; C( D/ d6 G2 }2 g8 Z
v;
/ h I! f8 H5 E: |9 w) O/ N9 Q
s(k+1)=v;
( _& C! E( ?( i7 z1 u( e$ l, X9 R1 I8 t
k=k+1;
; q& {) c: n6 n$ V0 P
u=s(k);
: W8 e; k/ u. X
end
% A; J. J: u- ~
l
0 g. \; ^1 J% H% { Q- G
z
5 E' o2 P# p! z$ t, P
, p# _( J5 P" ^* W4 A' [+ W M
(2) Floyd算法
1 [9 t# {& P/ ^5 m7 h* l
road2.m文件源程序：
& l; C9 l+ Q: P6 P. c$ J
a=[0 1200 inf inf inf inf inf inf inf inf;
, T" ~7 F3 H2 \0 J
1200 0 12 202 inf inf inf inf inf inf;
: x- w, l! E5 Y0 D* Q& I; a/ X
inf 12 0 inf 201 inf inf inf inf inf;
# \% R. X. a) z w4 _. q
inf 202 inf 0 31 20 inf inf inf inf;
7 K" }6 r2 v" ^% |$ k" G
inf inf 201 31 0 10 inf 205 inf inf;
4 E' E6 `7 H' w0 B
inf inf inf 20 10 0 195 inf inf inf;
, ~ _6 c2 t$ V9 u* J; [
inf inf inf inf inf 195 0 5 306 inf;
' q9 q4 m' Y( P; _; S! L z v& ]% m
inf inf inf inf 205 inf 5 0 inf 194;
* `! ^. P( Y+ i/ o6 J. n0 v
inf inf inf inf inf inf 306 inf 0 10;
1 R) [. c( U+ P, v- m/ _
inf inf inf inf inf inf inf 194 10 0];
2 B s1 Z. S5 ?% n3 p# \
[D,R]=floyd(a)
9 [/ E9 Y/ o7 x
floyd.m文件源程序：
- `+ O5 F, K# g) n
function[D,R]=floyd(a)
J7 k, w _* U& I
n=size(a,1);
) _: J4 I' D7 h! i: g- Z- @- q
D=a
H! d ~* b7 E8 q
for i=1:n
! [ |) A; T# n
for j=1:n
4 R+ S/ g3 b6 T4 R& C9 }
R(i,j)=j;
' v. n }- P2 N9 ^9 L) d
end
( Q) O+ ~/ p& y% }
end
2 z3 [2 I+ w- ?9 ~6 U
R
. ~, K" x1 v* ]: m- ~
for k=1:n
" x5 x+ e- A M9 p8 P9 ^9 @
for i=1:n
9 I0 o8 V/ f" u' ~& u
for j=1:n
8 }6 X1 H7 E' o, G2 b5 W, `1 N& P
if D(i,k)+D(k,j)<D(i,j)
* r, l5 a! K7 L" W0 Q- I5 h7 v, S
D(i,j)=D(i,k)+D(k,j);
9 d1 z* I: \9 U
R(i,j)=R(i,k);
& e1 C% R% H/ z$ H3 _
end
1 F, }" f0 o. \/ A' D9 e# |: k: P
end
2 q5 z& Z+ v5 b" P9 x
end
; C4 M: w& t' G# r% X5 s/ c
k
3 f! S/ C8 G+ H0 c* g; U* {7 K
D
: F' j6 b2 L) U# }3 T p
R
) {" F" ?# W7 v1 F! p
end
) Z6 f: {5 X5 ?' t: j
五．结果分析
; Z3 M3 Z5 Y4 T: j* e8 \
(1)Dijkstra算法
6 B0 u) z* y d8 p9 w! d8 `( b
运行结果：
9 x1 a) E9 w5 z- b3 c8 g0 L
l = 0 1200 1212 1402 1413 1422 1617 1618 1822 1812
* _; ]0 h' [+ {
z =1 1 2 2 3 4 6 5 10 8
1 w) y" } {$ X
5 R- @- K4 `+ g/ @6 ^
结果分析：
. F$ \! t- G0 Q
通过运行结果： 到其他顶点的最短路的权 ，可看出，
) W8 y/ a6 q {9 Y/ ?- f
到 (即 到 )的最短距离为1812(km)；
% t L) P% h6 w0 L* i
到 (即 到 )的最短距离为1618(km)；
9 m. C# R% t p
4 W$ M2 K. E y0 f- w, O
到 的最短路径为：V1→V2→V3→V5→V8→V10；
6 R/ V% z5 u }' T' ]. p
到 的最短路径为：V1→V2→V3→V5→V8。
+ H" }5 y" y7 F, d
1 C% w. e+ \' H" J
(2) Floyd算法
5 g1 J8 Y$ `5 n" y
运行结果：
* X) { |9 Y- x, [7 n( w% Y6 W4 ~
D =
& ]$ V' B" a+ {, r
0 1200 1212 1402 1413 1422 1617 1618 1822 1812
: i: Z: S/ n7 g$ F* r1 y
1200 0 12 202 213 222 417 418 622 612
* h$ s6 a- l: E1 l. l
1212 12 0 214 201 211 406 406 610 600
6 K/ J4 k7 k) J8 ]& J
1402 202 214 0 30 20 215 220 424 414
1 V: }5 K+ d w- \2 n* H3 u" o) M4 F
1413 213 201 30 0 10 205 205 409 399
, A N6 D/ C0 I# t9 e- X
1422 222 211 20 10 0 195 200 404 394
$ Y) x T V8 n8 T
1617 417 406 215 205 195 0 5 209 199
* x# C) {4 n$ e7 \3 I
1618 418 406 220 205 200 5 0 204 194
3 a/ o4 s5 S6 R7 b4 Y
1822 622 610 424 409 404 209 204 0 10
; m! |1 v% `$ b3 |; M1 z* X. Q/ ]
1812 612 600 414 399 394 199 194 10 0
: w+ X) K( k7 h* `( l
9 K* L3 A4 l. o+ F! |( X0 p+ m1 y/ ?3 T
R =
, G( r2 S+ c& ^ F
1 2 2 2 2 2 2 2 2 2
4 W1 H$ D9 q; _! K4 Q
1 2 3 4 3 4 4 3 3 3
3 J. n# X0 P8 p" q& D& o+ a
2 2 3 2 5 5 5 5 5 5
; Q, A+ [8 L' v
2 2 2 4 6 6 6 6 6 6
, [- X) T, y& D. p& i
3 3 3 6 5 6 6 8 8 8
9 F$ _; F& T. k: @: _; G
4 4 5 4 5 6 7 7 7 7
K4 `# @$ o& T6 C/ t, n5 _
6 6 6 6 6 6 7 8 8 8
- a1 G$ ]8 r# j, R. Y) |* g
5 5 5 7 5 7 7 8 10 10
. g& c% s, b! g9 D5 r
10 10 10 10 10 10 10 10 9 10
0 m- P6 e2 I/ q, j& y" S
8 8 8 8 8 8 8 8 9 10
/ D* O+ p* D+ ^4 a2 ]
结果分析：
H) c: P$ M: _) E% ~ l5 {2 \$ I( i0 s( E
通过运行结果：可看出，
# [* {: [5 A) K6 ?4 a0 N
到 (即 到 )的最短距离为1812(km)；
( p- x: b) p: T& L# @
到 的最短路径为：V1→V2→V3→V5→V8→V10；
3 r7 j" b# i1 v5 T* c) D& }3 c
到 (即 到 )的最短距离为1618(km)；
% M5 q2 I" b+ x* J$ R
到 的最短路径为：V1→V2→V3→V5→V8。
; H, _: b$ d* x; a- R0 Z: w
7 ^# v+ ~# _0 m I
( u4 \" ?+ r5 O$ z2 m! U
作者:
1430644259
时间:
2018-8-9 14:50
66666666666666666666666666666
8 x1 }7 e: ]8 V& D# ~- N5 ?
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
;