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

浅夏110

1 两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。

1 _3 l' k9 v6 S1 L, H' x: \
+ G9 z3 I6 o( f7 ^' a+ F) p
+ r/ I4 @1 h) e8 d" cDijkstra算法


例1  某公司在六个城市 中有分公司，从  到  的直接航程票价记在如下矩阵的  位置上。 （∞表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价便宜的路线图。               


0 ?2 ?( {7 z& H; Z! x
5 i' J% h3 S6 o4 k4 P解  用矩阵  （n为顶点个数）存放各边权的邻接矩阵，行向量 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分量
# G" w# Z0 W6 @+ I9 E" y3 F4 ?& U, @3 k
* K) [& J& U5 r  D
9 n6 a' U: [- X$ J2 ]- H7 ^
+ ~4 z( J1 }+ w9 k5 D8 _+ m求第一个城市到其它城市的短路径的 Matlab 程序如下：

clc,clear
6 j1 P; n3 m' R2 c( y2 l) N' l2 ha=zeros(6);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
; U4 g) f% H3 R+ P; Z% ma(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
3 R( D; a% a! Ua(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';
a(find(a==0))=inf;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;temp=1;
- ?( x" i8 h' R# f& Pwhile sum(pb)<length(a)
9 Z* j5 v9 l1 K$ i    tb=find(pb==0);
; }: f$ C; d- @, _. _" o4 x: M4 z    d(tb)=min(d(tb),d(temp)+a(temp,tb));
. c; Y$ @0 j+ u; S9 ^' c- Q' W+ l    tmpb=find(d(tb)==min(d(tb)));
) Z" _7 R9 r! r5 b    temp=tb(tmpb(1));
    pb(temp)=1;
5 n- G# e! x" B    index1=[index1,temp];
8 F4 h0 a7 t8 m) l5 p/ G. I    temp2=find(d(index1)==d(temp)-a(temp,index1));
    index2(temp)=index1(temp2(1));
. w# n9 n5 p% A7 ~6 E' |5 aend
1 P8 P9 W7 P, e  t* o; qd, index1, index2
' o: @" }( v9 n4 I3 S+ B' v7 S) v
9 {/ _! K3 C. l0 j1 Q! f  H2 两个指定顶点之间最短路问题的数学表达式


例 2  最小价格管道铺设方案
在图 3 中，用点表示城市，现有 A, B1, B2 ,C1,C2 ,C3 , D 共 7 个城市。点与 点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市 A 到城市 D 铺设一条天然气管道，请设计出最小价格管道铺设方案。

2 y9 }6 ]- \) M" p4 @
) {/ e. X9 u- \0 @* h( m) s
3 ~- L2 `! ]0 ^# r编写 LINGO 程序如下：
! l) p1 X8 }$ s
model:
sets:
cities/A,B1,B2,C1,C2,C3,D/;
! Z" N( p4 ?4 y+ m7 Kroads(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;
endsets
data:
w=2 4 3 3 1 2 3 1 1 3 4;
enddata
. S% F: @) E% G3 \2 |3 Q& C" Vn=@size(cities); !城市的个数;
3 p+ R7 b* R% V$ dmin=@sum(roads:w*x);
$ H  y, \6 X% L5 b$ a& \@for(cities(i)|i #ne#1 #and# i #ne#n:
    @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));
1 c/ y7 i3 r8 a    @sum(roads(i,j)|i #eq#1:x(i,j))=1;
1 \5 z- w8 y( E6 W+ _2 `    @sum(roads(i,j)|j #eq#n:x(i,j))=1;
end

! S; Z! A& w) D4 |* x% O: ~/ W例3 （无向图的最短路问题）

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

* E6 p; S* G7 q& m
$ A. d1 N4 K3 g' h, |' Y9 W
编写 LINGO 程序如下：

" ^( _& t4 U& k; F) a% bmodel:
. @( Y# F+ R- L1 u  c: ssets:
' P! P0 r( K/ {& z. J" S! vcities/1..11/;
0 t; p% O! ~7 o- iroads(cities,cities):w,x;
' p9 l- G5 H8 g3 Qendsets
data:
w=0;
enddata
calc:
, l1 w9 u& X' W; {6 @( L, H5 |w(1,2)=2;w(1,3)=8;w(1,4)=1;
' L. I6 Y% m0 E1 C9 mw(2,3)=6;w(2,5)=1;
- k, X: \1 @7 c6 O0 I2 I: }( Gw(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;
w(4,7)=9;
  M7 x; m, m3 C- t  J/ Yw(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;
7 y0 X; ]% f4 v/ V* C* L0 z% nw(8,9)=7;w(8,11)=9;
  k% `: f- |5 Lw(9,10)=1;w(9,11)=2;w(10,11)=4;
@for(roads(i,j):w(i,j)=w(i,j)+w(j,i));
: _# {) T8 S: z@for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j)));
endcalc
n=@size(cities); !城市的个数;
7 m' F# [/ q* K9 B4 u# Kmin=@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)));
* }5 ^# w5 {- d; B& s@sum(cities(j):x(1,j))=1;
- @9 p1 V( g1 a8 R' [  R& n7 H  e@sum(cities(j):x(j,1))=0; !不能回到顶点1;
  U0 X  G7 c: [$ Q# q8 {$ T3 r@sum(cities(j):x(j,n))=1;
@for(roads:@bin(x));
end
4 l. G& F9 }* J. I
4 `+ _+ a) v" I! F1 n6 \/ V# d有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即 从顶点 1 离开后，再不能回到该顶点。

& a$ S5 f6 z$ K: f) G" U求得的最短路径为 1→2→5→6→3→7→10→9→11，最短路径长度为 13。
' G5 v! o8 p- V+ X# u7 h
$ @# e) @; z5 \' K4 Q3 每对顶点之间的最短路径
0 M# X, Q3 I2 P$ ?) `  y计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。具体方法是： 每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反 复执行 n −1次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法 的时间复杂度为  。第二种解决这一问题的方法是由 Floyd R W 提出的算法，称 之为 Floyd 算法。

Floyd算法
$ ?1 _. c2 ~' y! n* S+ S

) R4 Z! p" o9 }$ ^& N
) g  E9 z( X0 \. {( W6 i+ V

————————————————
  ]: I4 i8 n7 m. l! |5 N1 n' ^. R版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785373
8 Q( h/ L  z/ X: ]7 W+ V, A
6 f& Y  j, N0 g
! V) x% C# s) ]6 N* p: G

德古拉

good try~~
2 g1 g7 R  O4 U: L3 d- A% y# s  }) @

浅夏110

德古拉 发表于 2020-5-20 08:06
: ]  d# e; L: _, k- A7 Ogood try~~

0 f9 u8 k5 [* a5 D; h8 v; `) S

浅夏110

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