- 在线时间
- 0 小时
- 最后登录
- 2018-6-6
- 注册时间
- 2018-6-6
- 听众数
- 1
- 收听数
- 1
- 能力
- 0 分
- 体力
- 21 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 14
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 14
- 主题
- 2
- 精华
- 0
- 分享
- 8
- 好友
- 2
升级 9.47% TA的每日心情 | 慵懒 2018-6-6 10:42 |
---|
签到天数: 1 天 [LV.1]初来乍到
|
最短路问题及其算法
0 g! Z2 x0 h$ D- d" R' I一.实验目的:( G7 q" s8 R4 O: C* C `" g7 L; b
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法;* ?' K& ?! a* K( s4 t2 B0 }. b
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.1 l# y7 z1 }8 [1 h% Z
二.实验内容:# b: {( K! l" r3 F
要铺设一条A1→A2→…→A15的输送天然气的主管道,如图所示.经筛选后可以生产这种主管道的钢厂有S1,S2,…,S7.图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位:km).
! B* A' C# @ t9 T" P! E为方便计,1km主管道钢管称为1单位钢管.
- G* I5 R: R& A/ @! _8 W一个钢厂如果承担制造这种钢管,至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元,如下表:
& T1 e/ o) b3 `! B( M8 v
! Z7 o& K5 ^4 N3 C& k }1 2 3 4 5 6 7
% p% b M( ]4 D8 c
* {( ?: z/ H- C) x800 800 1000 2000 2000 2000 3000
/ F" K% o5 ~9 W, ] 9 p8 I7 r0 K1 \& Z. L2 _% J# a
160 155 155 160 155 150 160/ Y9 Z( p' _4 |0 E( Z
W2 B1 D0 D7 V1单位钢管的铁路运价如下表:
+ L. j* K) I4 r里程(km) 300+ {$ m9 Z+ C4 @
301-350 351-400 401-450 451-500. `& n3 c0 E3 a- F' B
运价(万元) 20 23 26 29 32
- W0 y1 i b* U* X Q里程(km) 501-600 601-700 701-800 801-900 901-1000
; B0 X' U+ b2 ]0 I \9 T/ u运价(万元) 37 44 50 55 60( v/ z& B9 ^+ u( u
1000km以上每增加1至100km运价增加5万元./ `. J d/ Z4 j8 c
公路运输费用为1单位钢管0.1万元每千米(不足整千米部分按整千米计算).
7 d- M5 o h+ E; q% [0 z假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位,钢管出厂销价1单位钢管为155万元.
* n" P3 R, ~3 t5 [ I4 [
3 P" \7 Z' @6 s" V6 j试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划,使总费用最小.
. U" z. b2 o2 S, q: O三. 模型建立 b' d8 b$ u; i) U8 R
设 为 ,将上图按从上到下,从右到左的顺序依次命名如下.将上图改为如下赋权图形 :
& L) L. ]5 f0 Y
t' m9 m. t" M% O! J5 r利用Dijkstra算法和Floyd算法:求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离,即为 到 和 的最短距离
' {4 U+ Y% c/ d1 o/ u6 |4 q# ~
5 ?2 i8 C. ?, k& @! x0 g8 E3 Y7 k$ V解:先写出带权邻接矩阵:/ ?6 a' d8 e8 h% A2 E: m5 J1 S
) B& y5 k+ a& O2 F0 e' L后分别用Dijkstra算法和Floyd算法步骤,求出 到 和 的最短路的权 以及 的父亲点标记 .
; @& b _: `4 u1 `8 R1 B+ g四. 模型求解(含经调试后正确的源程序)* K* T/ d i+ P( V3 s& ^# @
(1) Dijkstra算法
s3 w3 W5 J- Oroad1.m文件源程序:8 Y+ k& @! H) D5 j; S% P. F
w=[0 1200 inf inf inf inf inf inf inf inf;
2 v/ B4 Q( ~/ T: m2 l* y1200 0 12 202 inf inf inf inf inf inf;* [2 X5 `3 z h9 s( T
inf 12 0 inf 201 inf inf inf inf inf;' U0 ]" E* H* p( s: h7 }
inf 202 inf 0 31 20 inf inf inf inf;
5 W3 x0 ]8 M5 k8 O4 E% s- S8 \inf inf 201 31 0 10 inf 205 inf inf;# Y4 I4 H6 u- G3 f
inf inf inf 20 10 0 195 inf inf inf;
, O5 |3 I9 R0 ~' ? N2 L& J; S xinf inf inf inf inf 195 0 5 306 inf; {9 b7 T% N& u, W- `4 z' A9 c
inf inf inf inf 205 inf 5 0 inf 194;' C% ?1 {- v) `1 M% i6 j' m2 {
inf inf inf inf inf inf 306 inf 0 10;
2 ~! Q6 E% b" H2 W% P6 c. B4 jinf inf inf inf inf inf inf 194 10 0]; & `9 h6 M) f( n! z z; I
n=size(w,1);
4 C2 B9 Z8 a! G Y' D k z2 _: L- iw1=w(1,;" ^" j% }. ?6 _8 }( E
for i=1:n' E4 D' V9 J3 }7 c2 I$ q# X# `
l(i)=w1(i);4 z3 s: G6 ], A) l9 g8 {6 ^
z(i)=1;# v7 H8 s3 }$ k: F
end
: B& L1 L; t$ g& y; es=[];
# }% ]" H( Z% }, \# Ds(1)=1;: }% ~% S4 a+ t+ P/ j3 O, a
u=s(1);7 w+ I' Y% E/ h. c* e8 e
k=1;+ F. u$ M9 l6 Q8 t4 u: \
l;
) O* I8 D& H; w0 J/ az;
) [4 f; g7 C/ j! U! `! Iwhile k<n j7 _& _3 N9 X" l# L3 r1 [- s3 U. I
for i=1:n) I: ?; H- X; t2 q% \
for j=1:k
7 P% s5 R- a- T if i~=s(j); u" v: _! u* Y) @1 H( o x
if l(i)>l(u)+w(u,i);
% b" t7 L6 n' q$ I5 o l(i)=l(u)+w(u,i);
, y5 G2 t" G% C- t% T: q% v z(i)=u;4 R+ K- f: G( s. i+ @0 W1 P2 T
end
3 w, N, H4 @- t; D) p+ G& H end% ^3 ~9 C: x- p2 W/ B& g r
end# J! K" w. ]6 a U7 `
end
& _- X4 A; h4 T l;& g9 e) {( W9 z8 E; Z: M, d
z;
$ W7 ^' r' {( `6 Zll=l;; s$ d0 g, G/ w
for i=1:n3 F. H: U7 C. R( W1 e$ C% m
for j=1:k
5 V4 [9 `1 u K if i~=s(j)
9 H" C( F0 @6 p ll(i)=ll(i);. N. `9 l. |( U, c1 E% J( ^
else
+ f9 a" @$ @9 w6 @6 f1 R, E ll(i)=inf;9 w3 U5 G6 U: B
end
1 V. z0 n4 i: l3 A5 cend
! n' @ n; L4 p! c9 Qend
$ `" D! B6 t& N0 z2 b) C5 Hlv=inf;
- X9 t; O- |% A; Jfor i=1:n& @' d( M: G0 \2 ^7 [" X
if ll(i)<lv
" @: @9 v1 V9 h lv=ll(i);, Q3 s" i, d c# \# D+ x# b0 z
v=i;; q) Z, T+ D0 c+ L$ `& y
end( X6 Y) i- h# P
end
# n; F; k$ D+ Z7 F& blv;
& W# g B- y2 M8 p0 n+ cv;
9 O9 Y2 _8 }; q- w! ms(k+1)=v;3 C8 R1 t% q8 \* z O3 Z1 Q2 ^ c
k=k+1;
& x9 h3 c |+ u2 P# a5 D$ n+ du=s(k);7 J" M9 {( m! L5 D' }/ |$ z; {' D
end
- W& h9 {1 q7 I2 } {, o( r) gl
3 U/ r$ S2 G# {3 R* Mz
# X8 j% k. G& s, T$ j7 v2 `) y4 Y' _* ?# k5 h- {1 h
(2) Floyd算法
$ r/ c+ Y( F1 z$ C6 @% R3 \! U! S: Mroad2.m文件源程序:7 G7 H( E: C( l4 L6 r2 n5 B( U
a=[0 1200 inf inf inf inf inf inf inf inf;. e, h. M' N# l" U
1200 0 12 202 inf inf inf inf inf inf;" _. d1 Q8 y: g% l0 C" _
inf 12 0 inf 201 inf inf inf inf inf;, @# j* i }6 r, c2 s% \, @( I
inf 202 inf 0 31 20 inf inf inf inf;4 a- j: y$ K) M; x' H1 ?
inf inf 201 31 0 10 inf 205 inf inf;
8 `0 v! N! P8 d: h9 _4 Xinf inf inf 20 10 0 195 inf inf inf;
! r/ R' Z: L% [) j$ ^inf inf inf inf inf 195 0 5 306 inf;
, y R" [% N3 x$ i& g* P5 Ainf inf inf inf 205 inf 5 0 inf 194;
1 A# e$ P+ u7 \# Ginf inf inf inf inf inf 306 inf 0 10;
, {$ p) [. [: Z T ^4 Ninf inf inf inf inf inf inf 194 10 0];
/ e0 |3 Y+ h' s/ v2 G. X[D,R]=floyd(a)
- c! e. J; | w8 g cfloyd.m文件源程序:3 H6 _, ]9 s3 }2 z& l2 V
function[D,R]=floyd(a)
5 b: X- H( i) L( Wn=size(a,1);$ T6 Y: Z. T3 R- W0 B$ {, u
D=a; f. E4 ~* c$ B2 ?# O3 J
for i=1:n( _4 J8 B7 a. R- k+ G
for j=1:n
8 ^' S" D! E$ ]* @ R(i,j)=j;" D. G( A/ M: A
end
, \8 @: ~% f5 ^4 i7 r) Aend
H1 Y( |' g$ ^' T5 ZR
' h4 |% R# m3 F) r! Zfor k=1:n
: B" f' T- f; C4 k" s0 ~' q0 v for i=1:n
' A5 d# Z0 r( ?8 G for j=1:n
: H5 U( W6 v( Q# j; B& C6 @5 q1 S if D(i,k)+D(k,j)<D(i,j)
0 j# s) u( q. G# J. i6 \& m, i D(i,j)=D(i,k)+D(k,j);! J) `0 F) [5 E# D' g) V
R(i,j)=R(i,k);" e) D% r9 q/ }: ]* H: b% J
end
% Q8 a f# q1 U3 T& ?- w end
+ q6 L/ z/ O) T& Q3 N" w6 Z# Z8 w2 Z& A end
* g7 l9 u2 a2 y. z k
; E* w2 J3 z0 X8 }. N; H" ? D
% X% |' x5 m- l R# y& ]) f" |0 O6 V: h
end
+ j h4 d. {% Y9 N$ P五.结果分析
0 U2 F# J, C# K9 r9 P5 N$ R! p. D" g(1)Dijkstra算法
: v. {. ]# m, I" i. P" y! P# a4 f运行结果:
. @+ {; E& R, d3 Q7 Ql = 0 1200 1212 1402 1413 1422 1617 1618 1822 1812
" j! M0 R3 J' }& pz =1 1 2 2 3 4 6 5 10 88 T; R, U8 o0 r! i# ]6 R& j6 N. X
5 l- i, ~8 W: T1 c; N
结果分析:/ k8 t" J% A$ z. R# H
通过运行结果: 到其他顶点的最短路的权 ,可看出,) G6 c9 E) w0 j$ N* V
到 (即 到 )的最短距离为1812(km);
& E7 C) H. I. ]8 G9 R 到 (即 到 )的最短距离为1618(km);
1 ^3 y" D0 @9 v3 C4 O' m' `/ v1 F7 f* s. S# t9 z' o! ]
到 的最短路径为:V1→V2→V3→V5→V8→V10;. e) E, l* Y) m/ _& J
到 的最短路径为:V1→V2→V3→V5→V8。( {' }' D' T* i- ~: E
; W* V" V/ K" ?7 M(2) Floyd算法
$ }4 z9 O" @1 K( L* R. c3 d运行结果:6 \/ \, M' P, t5 G3 g* ~
D =. l7 V S; I; V! c2 t
0 1200 1212 1402 1413 1422 1617 1618 1822 1812
6 f$ s d8 U' n3 G 1200 0 12 202 213 222 417 418 622 612
3 w! h; a* S# ~% d 1212 12 0 214 201 211 406 406 610 600
/ h4 o+ r8 w- j 1402 202 214 0 30 20 215 220 424 4145 d; W$ b( ~/ d% k0 H6 X5 h
1413 213 201 30 0 10 205 205 409 399; w. m; p+ p! X0 n8 Z( P
1422 222 211 20 10 0 195 200 404 3947 M& {9 h, V: T0 I# V6 V
1617 417 406 215 205 195 0 5 209 199
4 y# h& y( T/ {( ~* P f; Q. }9 K 1618 418 406 220 205 200 5 0 204 194
1 l* M$ ^$ w) W- I# S' i; v 1822 622 610 424 409 404 209 204 0 10- {. Y, }( ^# v+ \5 R
1812 612 600 414 399 394 199 194 10 0
6 h1 F1 n. I: j5 t
% _( h$ p/ t I. @9 uR =& b/ N. J1 j6 Y! ]8 @$ `, ?6 }
1 2 2 2 2 2 2 2 2 2
0 j3 W! @/ w4 ~0 ^- h8 H- p8 R0 p6 ~ 1 2 3 4 3 4 4 3 3 3
, L2 \* e+ T! @0 t& }" d) T 2 2 3 2 5 5 5 5 5 5$ Z9 M+ M0 Y! T$ d* q/ b
2 2 2 4 6 6 6 6 6 6. w) t& }* E" {+ O; ]0 }
3 3 3 6 5 6 6 8 8 8, ~6 K0 ^7 m# h. t
4 4 5 4 5 6 7 7 7 7& f& W& b" E, ^6 I
6 6 6 6 6 6 7 8 8 86 `( i! z2 w9 c+ V- [
5 5 5 7 5 7 7 8 10 10
. ]5 ]6 O' w1 V1 D6 D 10 10 10 10 10 10 10 10 9 10+ \9 q( Q7 P% c
8 8 8 8 8 8 8 8 9 10
6 R# o% w7 S, E8 k# d: E ^ k结果分析:
4 w, G: S+ N+ Q$ s7 t通过运行结果:可看出,
4 p* M& p0 Z+ m% m+ ]: {# C 到 (即 到 )的最短距离为1812(km);
* [6 S% }# ]# D: O 到 的最短路径为:V1→V2→V3→V5→V8→V10;$ V% G; {! g6 c8 u% v
到 (即 到 )的最短距离为1618(km);/ y4 D9 R2 M; w! w
到 的最短路径为:V1→V2→V3→V5→V8。7 `) n9 N) v, B s& _
2 O0 L: k0 }, J, S7 q
' ?, m) v& H- T% I6 t @" Y/ } |
zan
|