常用模型&算法总结—图&网络模型应用—最短路径问题

浅夏110

1 两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。
. K$ }6 ?" p- O8 d/ I
0 i  ~; g5 |( R3 f+ Y+ d; O

Dijkstra算法
: @' Y( |$ p& B' I

例1  某公司在六个城市 中有分公司，从  到  的直接航程票价记在如下矩阵的  位置上。 （∞表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价便宜的路线图。               
- m; ^$ |* X) M8 O9 i% t: M/ S
2 t/ _- ^- t3 X' P

7 v1 h  T5 x% c$ k解  用矩阵  （n为顶点个数）存放各边权的邻接矩阵，行向量 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分量

7 f7 k) r- Z' b
" H- O! H/ |7 \1 l) s9 z  \+ [' H& \; P
/ Q0 b7 ^* L* R0 ^5 ^# F' h" `  N求第一个城市到其它城市的短路径的 Matlab 程序如下：

. }" N, @: E0 y2 t* f$ Dclc,clear
a=zeros(6);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
9 `" Q7 z" H& @+ e' ea(3,4)=10;a(3,5)=20;
& C5 ~; L- Y8 j/ h2 qa(4,5)=10;a(4,6)=25;
a(5,6)=55;
3 }4 q2 Z/ v* l* c& @a=a+a';
a(find(a==0))=inf;
6 U! f" o" l' ]' T; h. Hpb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;temp=1;
% B; F% j4 I8 y  l) X/ s6 {while sum(pb)<length(a)
2 ^) l1 |- U# s& }    tb=find(pb==0);
    d(tb)=min(d(tb),d(temp)+a(temp,tb));
    tmpb=find(d(tb)==min(d(tb)));
    temp=tb(tmpb(1));
7 `" Y9 D" V! `5 s    pb(temp)=1;
1 H. i( l2 @, y" S    index1=[index1,temp];
( B5 K$ I3 ]. v7 n) j* D) R    temp2=find(d(index1)==d(temp)-a(temp,index1));
. _2 ~7 K& H0 g    index2(temp)=index1(temp2(1));
end
d, index1, index2
6 t  t6 R. ~! w* L7 d
2 两个指定顶点之间最短路问题的数学表达式
* ^. M4 ~5 T' a0 P; W: i' `

, }  p3 k- P9 o. z例 2  最小价格管道铺设方案
: u0 b( c& W7 h$ m# \3 t3 h在图 3 中，用点表示城市，现有 A, B1, B2 ,C1,C2 ,C3 , D 共 7 个城市。点与 点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市 A 到城市 D 铺设一条天然气管道，请设计出最小价格管道铺设方案。


' p: H- w1 r- h2 v% M
编写 LINGO 程序如下：

model:
sets:
" Y* G& C, K7 r5 L7 b. d3 Gcities/A,B1,B2,C1,C2,C3,D/;
1 H9 y# X% ^" a" ]8 T* u4 |* I+ Lroads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1,
B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;
( L2 t) B( x2 Q( z- M( I, E( d1 Iendsets
3 D1 }% e! _% a% [: y$ @9 O% q) Vdata:
/ ], g- u- u4 R% I' hw=2 4 3 3 1 2 3 1 1 3 4;
' h0 Q( b$ N9 P. S1 M( ]5 j, y4 \enddata
n=@size(cities); !城市的个数;
3 K; j2 G2 P1 \1 h- i( y/ ~7 ~' emin=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#n:
    @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));
2 }( N- R: x& p) W9 f, y; p; q6 |    @sum(roads(i,j)|i #eq#1:x(i,j))=1;
    @sum(roads(i,j)|j #eq#n:x(i,j))=1;
end

, M4 f4 }# D, }( E4 T7 {2 T9 b例3 （无向图的最短路问题）

求图 4 中 v1 到 v11的最短路。 分析 例 2 处理的问题属于有向图的最短路问题，本例是处理无向图的最短路问 题，在处理方式上与有向图的最短路问题有一些差别，这里选择赋权邻接矩阵的方法编 写 LINGO 程序。

$ i# p0 G! `( Y4 W( [( k" @
( e  v  B# ~% Z0 S+ q
编写 LINGO 程序如下：

9 `, N. d. B) E1 g6 kmodel:
( S' ^$ u3 V6 D0 B2 Y0 qsets:
. f/ t/ q( O; X: N- \# q9 W5 B3 t9 ycities/1..11/;
roads(cities,cities):w,x;
endsets
5 c0 F" Q$ d- H) o. Edata:
3 }5 t8 ]6 l! a$ t% \/ B; Xw=0;
enddata
calc:
; P/ `! u1 g. ^4 V/ x( @: l7 Lw(1,2)=2;w(1,3)=8;w(1,4)=1;
# R! _: a3 m( r+ e; k9 g$ t9 Vw(2,3)=6;w(2,5)=1;
w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;
7 ~" r$ x4 N8 M& Ew(4,7)=9;
# y- D' [/ t$ {) X3 m- I: j/ Ww(5,6)=3;w(5,8)=2;w(5,9)=9;
w(6,7)=4;w(6,9)=6;
w(7,9)=3;w(7,10)=1;
w(8,9)=7;w(8,11)=9;
# m+ _% ?7 q7 j! C4 bw(9,10)=1;w(9,11)=2;w(10,11)=4;
@for(roads(i,j):w(i,j)=w(i,j)+w(j,i));
+ H+ @: @. Z# C+ q! K% [) i0 R@for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j)));
endcalc
n=@size(cities); !城市的个数;
$ p* r& s% o  |. s- Imin=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#
n:@sum(cities(j):x(i,j))=@sum(cities(j):x(j,i)));
& `! q/ P" ~9 b7 W0 U( ^@sum(cities(j):x(1,j))=1;
@sum(cities(j):x(j,1))=0; !不能回到顶点1;
6 j' y9 t6 Q5 I/ N@sum(cities(j):x(j,n))=1;
9 h; \5 |, t. s5 O@for(roads:@bin(x));
* U/ X3 j9 F2 z# f6 vend
- a/ F- Z) E9 t, F5 f# [
6 r% a, V: T$ L有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即 从顶点 1 离开后，再不能回到该顶点。

求得的最短路径为 1→2→5→6→3→7→10→9→11，最短路径长度为 13。

' n# G6 p9 S- t8 h3 每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。具体方法是： 每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反 复执行 n −1次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法 的时间复杂度为  。第二种解决这一问题的方法是由 Floyd R W 提出的算法，称 之为 Floyd 算法。

Floyd算法
3 i/ L$ h, G4 F; j
- X+ ?2 r5 K; P# g
% h) h5 c) A; w/ t$ T& z

8 R  l1 F" s% Y) {; T7 b
: m3 Z% h* S% ^# R/ n/ Y2 b————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# F5 Q) T( N$ ~0 x8 e原文链接：https://blog.csdn.net/qq_29831163/article/details/89785373

! J8 B+ I7 g9 ~+ }( r

% C, S6 G7 S8 j2 q
' o* k4 p- l4 a- L

德古拉

good try~~

浅夏110

德古拉 发表于 2020-5-20 08:06
good try~~

" I' {3 b* A, _# u* X
9 T9 b$ T  T$ Q1 c

浅夏110

德古拉 发表于 2020-5-20 08:06
5 ~8 |6 w' Q1 V7 u, ?5 Vgood try~~

& e8 g9 o5 y6 y3 M8 E8 P* \4 Z