数学建模社区-数学中国
标题:
最短路问题
[打印本页]
作者:
2395960434
时间:
2018-6-6 10:52
标题:
最短路问题
最短路问题及其算法
, }% `; q8 X/ U4 g
一.实验目的：
# ~4 i' T1 v0 ]9 S+ y
1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；
& d+ B6 m7 \' ^& k @$ ]
2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.
3 Q, a2 m( U( P. F
二.实验内容：
# u0 h* B7 E2 Q6 q0 R' B' X
要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.
$ g" u) I+ C6 E3 V' S# ^ X
为方便计，1km主管道钢管称为1单位钢管.
& q2 u' w. m; F2 c2 N: d
一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂 在指定期限内能生产刚钢管的最大数量为 个单位.钢管出厂销价1单位钢管为 万元，如下表：
+ @0 D" }4 W1 u. J* G2 R' ~
' B8 m) b n/ R6 R0 y' j- A
1 2 3 4 5 6 7
( h" B. X2 N1 L" G7 D
' @7 J: v* `2 n# c8 L
800 800 1000 2000 2000 2000 3000
" m! O3 e0 {" I% T
1 s2 ?* ?; M& f( h- Q# S) ~
160 155 155 160 155 150 160
; n6 M$ o' k) i; p: o& M5 A7 C% Y
3 l& B8 G; s, f! c. ]' h9 M" k
1单位钢管的铁路运价如下表：
* C. l# F( D2 h/ x2 ^
里程（km） 300
; T- a, r/ F' @" _8 Q+ N: f
301-350 351-400 401-450 451-500
2 z3 _& A! r1 d; |' k
运价（万元） 20 23 26 29 32
+ V# @9 V7 v. m9 `( t8 D& M5 W
里程（km） 501-600 601-700 701-800 801-900 901-1000
3 Y* f- E) `5 H% e5 j
运价（万元） 37 44 50 55 60
+ @6 w) |2 e2 `! x8 m, a: F. f
1000km以上每增加1至100km运价增加5万元.
" l$ ]* Y% R6 f/ U
公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.
5 { v) ?7 E$ h- Z& v& y
假设从钢厂 订购钢管运输到铺设地点 和 .钢厂 在指定期间内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为155万元.
M8 Y) D" D% V
2 D# s w0 q$ j6 g. W* o5 v
试制定一个从钢厂 到铺设地点 和 的钢管的订购与运输计划，使总费用最小.
( p8 @ G' d4 I; U
三. 模型建立
0 K) _8 b4 i: x! T
设 为 ,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形 ：
) C5 H& T/ i( K5 j. z2 `( m2 O
6 z# S2 g* l0 ]/ }
利用Dijkstra算法和Floyd算法：求 中从顶点 到其余顶点的最短路.而求钢厂 到铺设地点 和 的最短距离，即为 到 和 的最短距离
! _( |+ K' k/ A: ^0 }5 A
7 Q* f/ o/ K7 w+ ?2 ]
解：先写出带权邻接矩阵：
0 n; z) L0 q, j* n& Y! _
3 H# a- G3 e) k: t, t' a# [
后分别用Dijkstra算法和Floyd算法步骤，求出 到 和 的最短路的权 以及 的父亲点标记 .
/ n; \8 u h* D0 n
四. 模型求解（含经调试后正确的源程序）
) M% x% ]8 P9 M8 u; W! W% r) s M
(1) Dijkstra算法
7 i# o9 j! m* L) y6 \: Q
road1.m文件源程序：
7 [ |7 U4 C9 C2 ~
w=[0 1200 inf inf inf inf inf inf inf inf;
9 K7 ?6 h& h. v! Y$ k
1200 0 12 202 inf inf inf inf inf inf;
- g' Q4 P# [: V- ?" b9 e
inf 12 0 inf 201 inf inf inf inf inf;
: H1 W- e5 F; u+ P3 Q
inf 202 inf 0 31 20 inf inf inf inf;
) s2 E7 A8 X/ ]1 I
inf inf 201 31 0 10 inf 205 inf inf;
8 }# w. }0 y, x" g
inf inf inf 20 10 0 195 inf inf inf;
1 h0 J" c9 i- w
inf inf inf inf inf 195 0 5 306 inf;
9 F% h! w: J- N9 F# E$ Y
inf inf inf inf 205 inf 5 0 inf 194;
7 p$ T3 v+ `3 m" J8 }
inf inf inf inf inf inf 306 inf 0 10;
1 d9 X' r1 C2 y1 T3 w
inf inf inf inf inf inf inf 194 10 0];
4 l3 U" ~* o" ^4 A; T$ N$ O
n=size(w,1);
2 _6 o* j- y9 w, l( p& b6 z
w1=w(1,
;
3 S! `6 ~6 Y+ g
for i=1:n
/ `. @1 }7 P: Q/ a
l(i)=w1(i);
% M2 C8 R6 j- @' @% y: h7 F5 h
z(i)=1;
- s/ \1 _3 G9 K& f
end
$ i; d# c ^2 N1 j" Y5 ]% V
s=[];
0 }- f4 Q. _4 }; U A* g6 D
s(1)=1;
* \) U% ]# Z! b% m( b, @3 a" Q' l
u=s(1);
* W% k& J$ A- \6 O7 |
k=1;
: c5 p: ]4 H' i1 t+ a
l;
/ G" N% g- S3 }- u/ U
z;
3 B2 V+ l) a. E' E
while k<n
' E3 N7 C$ q% U3 v; e
for i=1:n
! S$ C2 q+ i& z6 X% H
for j=1:k
2 }* y) j( U) M7 ]8 s
if i~=s(j)
! v u9 t+ K% ?4 l% d4 B, o
if l(i)>l(u)+w(u,i);
0 O; B# X3 k' }
l(i)=l(u)+w(u,i);
W7 u5 b3 K8 o* R: q F
z(i)=u;
- [6 S3 p- S3 h- U; }+ p0 z1 X
end
- l, L) ^ t- N( W# d/ G
end
) |2 E0 l7 C: A0 o$ ~
end
% k6 l' p/ w* y h
end
2 I" s8 G' D: q; a: r; }! W' b
l;
/ Z/ @! S# i2 t) N, L- }- z$ x& f
z;
3 B9 k5 A6 ]* m; @2 p/ F
ll=l;
+ m7 ^. N; G/ ^
for i=1:n
9 t* ]0 i% z8 Z$ O8 L+ P+ Z. {
for j=1:k
0 g% y7 R# {" _; t+ j; ~- t$ j
if i~=s(j)
, g( H4 s( d; u
ll(i)=ll(i);
5 M8 }, X" G5 b
else
$ H7 d5 G4 [; t; e$ Q2 h0 `
ll(i)=inf;
* p/ z0 Y" _/ a# l1 B
end
0 q! K9 A2 ?# M7 ~# Q$ o' X
end
* u5 g" k6 R; s, Q% \
end
8 ^6 @4 F! g: z% y/ s, G1 t& L9 [ Y* f3 M+ i
lv=inf;
* }9 m) [/ f, Z* e5 S1 t5 z& x& g2 ~( l
for i=1:n
4 w. z: k4 C# I4 k5 C
if ll(i)<lv
8 Z: f+ e7 x) V4 A* @, {& G
lv=ll(i);
/ X: ^! T: U7 b) E9 q1 \& P
v=i;
4 @$ W* e. G( J9 R, L
end
3 D" B i2 @% G- g
end
- @- y8 e0 \" k
lv;
8 H- ?9 s- d: |( |7 O. K( {/ g
v;
. [# ?4 o4 d4 Y5 M8 L# G- Z; P
s(k+1)=v;
0 Y$ U% g/ ^' z
k=k+1;
# w1 s: X5 a5 n. n& N
u=s(k);
& t6 T% u1 `# P8 a) c; [+ P; d
end
1 _ e1 g( L u7 \3 M
l
' G. e6 D2 D7 t- a7 H: M# y4 |+ {
z
& Y- I/ a+ f( h# g* a, P9 k
* }/ o7 V t4 I6 r8 y% G2 p4 x5 F
(2) Floyd算法
* a% D# N7 g7 f. j
road2.m文件源程序：
! U+ t. E4 h. X
a=[0 1200 inf inf inf inf inf inf inf inf;
$ `' S( I+ ]1 L. E
1200 0 12 202 inf inf inf inf inf inf;
, d0 s- t# C+ k3 `0 p F
inf 12 0 inf 201 inf inf inf inf inf;
' D& l2 H5 x( h) S5 c
inf 202 inf 0 31 20 inf inf inf inf;
% _: `% V& @. P) f
inf inf 201 31 0 10 inf 205 inf inf;
" D8 f. T0 C0 d% f3 M) b9 }
inf inf inf 20 10 0 195 inf inf inf;
( E- K$ S( @/ C- S: n& d/ _8 _$ B
inf inf inf inf inf 195 0 5 306 inf;
! A# q7 `5 W1 V" V
inf inf inf inf 205 inf 5 0 inf 194;
1 E; h7 y5 G3 g5 @1 k) J! q! W8 L3 Q
inf inf inf inf inf inf 306 inf 0 10;
, o- }: a" C1 T: l: ]! y
inf inf inf inf inf inf inf 194 10 0];
, R+ H7 ]& e$ U2 @4 J3 n
[D,R]=floyd(a)
5 v5 H; u: q0 a
floyd.m文件源程序：
0 W( @0 {0 Z H: o0 W! ~5 @/ R$ n
function[D,R]=floyd(a)
1 t: h9 U/ t3 \5 |
n=size(a,1);
" U( a& _7 m" J- I
D=a
1 E/ T1 x6 S% ~
for i=1:n
2 \" d8 c9 X- l
for j=1:n
6 F/ B3 m, O; h) `4 J; ]
R(i,j)=j;
! d$ F# R* }. \' S* m2 k- L6 h) n7 n
end
. J, e2 V. z0 s7 ]$ O) E5 n; S
end
" h. w# o6 d8 G# u6 t
R
+ j: _( k( x, {3 T- @1 Z
for k=1:n
7 X1 C4 v* c& g; X$ s& F9 v$ W
for i=1:n
- c2 p0 `& ~& H$ q
for j=1:n
$ |0 u! _4 H, }2 [3 E5 ]
if D(i,k)+D(k,j)<D(i,j)
' Z3 m) A) ~0 P' q$ W/ i
D(i,j)=D(i,k)+D(k,j);
$ c1 E$ q3 z& u& Y7 s7 m T
R(i,j)=R(i,k);
/ _9 j ?( p7 k3 I8 V
end
7 |& A* b9 p, h7 G; @8 e# L
end
- p/ P" w8 K3 m' b4 R0 s' H
end
: X& C2 f: ]2 _ f* }
k
5 M9 K' \, B, `' ~& y) D# q/ F
D
! v3 p; O% _ w, H; y
R
' m) _, t: Q7 a' x
end
0 k: \$ K7 b8 _( ~
五．结果分析
9 _& ~* N, B; X7 e7 A
(1)Dijkstra算法
% _9 O( F) d, V0 [: a) ?( H
运行结果：
- t$ Q0 l8 M, J5 b* J
l = 0 1200 1212 1402 1413 1422 1617 1618 1822 1812
2 r3 x' C: c( r4 G5 D/ ?9 W
z =1 1 2 2 3 4 6 5 10 8
/ |; s/ V! D3 \. y$ C& E
r# w( h% t7 t. Y: M+ f# b
结果分析：
% [7 V1 P% a5 A8 n
通过运行结果： 到其他顶点的最短路的权 ，可看出，
% }$ |1 x6 ^( [7 u, `; E9 b) a
到 (即 到 )的最短距离为1812(km)；
8 P% R' `, Y. G' { a2 d
到 (即 到 )的最短距离为1618(km)；
& T" y. e0 k; O" f9 N, g* [
5 B6 g2 ~ ~2 V
到 的最短路径为：V1→V2→V3→V5→V8→V10；
0 g/ T9 o. \% x2 Q0 `
到 的最短路径为：V1→V2→V3→V5→V8。
8 z5 {$ \' V$ x0 V$ ^0 M
9 D3 ?- @6 N/ a5 R
(2) Floyd算法
/ i8 y' r2 T3 K7 S( q; ^9 s
运行结果：
9 ~0 Y. N! [1 a8 j9 I
D =
8 R( w: i- _, A+ N/ U7 C6 n+ L$ e
0 1200 1212 1402 1413 1422 1617 1618 1822 1812
' U2 j" [2 @* L- [7 z. b
1200 0 12 202 213 222 417 418 622 612
' l5 w; ?0 N) {5 n
1212 12 0 214 201 211 406 406 610 600
5 w+ U. } l* r; L: c1 F
1402 202 214 0 30 20 215 220 424 414
* b6 A: C& i4 h! a4 A
1413 213 201 30 0 10 205 205 409 399
! e ^/ R3 `3 N s2 m: V3 s" D
1422 222 211 20 10 0 195 200 404 394
# ~7 f/ q* l" G# m6 Q+ J y
1617 417 406 215 205 195 0 5 209 199
) {; }( E+ h- l/ o
1618 418 406 220 205 200 5 0 204 194
' y/ J8 I* Q& X, |2 r/ B: }; U
1822 622 610 424 409 404 209 204 0 10
/ N b6 ?' W ~4 w) Q' F1 X. W
1812 612 600 414 399 394 199 194 10 0
* y5 S1 O# Q+ g( M+ ]3 |
3 ]( [# ]9 N7 J) F) T
R =
3 Y* n$ e: [" t) N' V+ @3 s
1 2 2 2 2 2 2 2 2 2
9 y: U+ E# A8 \0 Y; r
1 2 3 4 3 4 4 3 3 3
$ |/ W( }# g' x P% n" @) v
2 2 3 2 5 5 5 5 5 5
: i- B5 u. p8 K' j' f. [0 i/ N
2 2 2 4 6 6 6 6 6 6
; u7 m8 `" u) o, |
3 3 3 6 5 6 6 8 8 8
: b& W1 b; t1 @( L/ A4 c
4 4 5 4 5 6 7 7 7 7
- x& I, ]# V1 ?0 F5 P& S$ E
6 6 6 6 6 6 7 8 8 8
0 s) j2 ]- n5 s. y' o. Z+ [$ n! l
5 5 5 7 5 7 7 8 10 10
/ r1 I; {" R6 E y
10 10 10 10 10 10 10 10 9 10
! Q t5 v" ~ b* ^- [* [" m0 r9 g
8 8 8 8 8 8 8 8 9 10
* ^0 [! H1 l* { ?& p- m
结果分析：
: F. k9 t7 ^! w
通过运行结果：可看出，
+ R& a& m2 N$ j# g
到 (即 到 )的最短距离为1812(km)；
; F! @! f$ @6 V0 a$ x: r
到 的最短路径为：V1→V2→V3→V5→V8→V10；
1 A9 Y& D# V* c, g, ]2 Q7 |# s0 r
到 (即 到 )的最短距离为1618(km)；
0 M9 X# h" r/ A+ X% m
到 的最短路径为：V1→V2→V3→V5→V8。
& \5 |/ t0 H" ] P& I" u) L" [
4 M G2 R3 L5 }) @& I
, E, L! g: f7 b& x
作者:
1430644259
时间:
2018-8-9 14:50
66666666666666666666666666666
& I4 ]8 s. D9 ^& d# U( S, [ \2 }4 r
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
;