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

浅夏110

1 两个指定顶点之间的最短路径
* ~, t# l& y, E- j' C问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。
5 V0 B8 W1 ~3 J/ M6 N0 F
- A6 w7 Q/ ~6 J: C: k2 [

6 i* z+ X& c3 C% x( u% ]# yDijkstra算法


, i7 R, u3 R" p) y2 v例1  某公司在六个城市 中有分公司，从  到  的直接航程票价记在如下矩阵的  位置上。 （∞表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价便宜的路线图。               
5 Y" y1 [1 E/ V, s0 ]- N% A
1 q- q7 \% e% ?" R8 }
9 K% I8 I- K* P) A/ ~
解  用矩阵  （n为顶点个数）存放各边权的邻接矩阵，行向量 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分量
  x* L8 U! ]: H& Y3 j2 O
( s+ s2 q  U/ Y$ }; U: v: ]2 k

求第一个城市到其它城市的短路径的 Matlab 程序如下：

8 _& M9 _: }+ D; }clc,clear
  N- t$ [/ w% ~+ ]& |a=zeros(6);
! J* `, l  n# Z$ ^0 da(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
  V/ l1 K( M6 j2 n! sa(2,3)=15;a(2,4)=20;a(2,6)=25;
, J0 S2 b& j! a: D" i/ Ea(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
7 A% e3 \5 M/ }: p4 L2 [1 Ma(5,6)=55;
a=a+a';
: Z2 r) M9 S4 \5 u9 s$ Pa(find(a==0))=inf;
1 I, y7 ]. p7 a; z$ ^, i  t9 }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;
1 R1 ^+ m" |6 @9 \: m# \0 Mwhile sum(pb)<length(a)
4 l  [/ t8 y& Q- `    tb=find(pb==0);
6 I1 J3 G. |1 N' Y1 `" l    d(tb)=min(d(tb),d(temp)+a(temp,tb));
    tmpb=find(d(tb)==min(d(tb)));
  u& A( h0 T5 m/ F    temp=tb(tmpb(1));
* s7 S* [; G1 r% J; r5 O( R& {    pb(temp)=1;
    index1=[index1,temp];
  Q2 }* ^) }% K2 ]" l% L8 O    temp2=find(d(index1)==d(temp)-a(temp,index1));
. a" a: ]1 [7 ?' O, }4 ~) a    index2(temp)=index1(temp2(1));
end
d, index1, index2

8 H! C  w6 L, [3 R2 两个指定顶点之间最短路问题的数学表达式

4 B# T: H* x3 M& F( [& l; d' z( w
例 2  最小价格管道铺设方案
$ ~( o& G5 z( ?7 n5 L4 B" a% ]在图 3 中，用点表示城市，现有 A, B1, B2 ,C1,C2 ,C3 , D 共 7 个城市。点与 点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市 A 到城市 D 铺设一条天然气管道，请设计出最小价格管道铺设方案。
$ C4 m. n3 U  s; t* n

; ]; `" K+ ~8 _( @% m# ?
' D: b" y1 Y8 w+ F编写 LINGO 程序如下：

9 g# O# c2 b* v* m( Z$ Hmodel:
sets:
cities/A,B1,B2,C1,C2,C3,D/;
roads(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;
7 k1 z7 o; D2 `endsets
6 E0 Z* A$ l8 [0 n3 F% K; ydata:
; N2 y, E3 ^9 m/ Hw=2 4 3 3 1 2 3 1 1 3 4;
8 ]/ r# [: `! B) i: |enddata
& s6 l7 Z' n4 ?( o+ b  O9 Rn=@size(cities); !城市的个数;
min=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#n:
! K3 a7 b" P# K* b. Z; V. J    @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));
    @sum(roads(i,j)|i #eq#1:x(i,j))=1;
    @sum(roads(i,j)|j #eq#n:x(i,j))=1;
end

+ b3 ~5 N, t1 T5 L1 z/ Q' C+ R例3 （无向图的最短路问题）

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

7 s. O: U  a/ s, j2 E编写 LINGO 程序如下：
5 U; ?4 V6 m& k3 B; ^" b" {# v: l
model:
sets:
3 D3 f  W2 V0 wcities/1..11/;
" O% ~/ }3 }, Y4 E% K7 [roads(cities,cities):w,x;
) s; u. I/ X) r2 A5 vendsets
data:
w=0;
* _; u7 J+ u9 [4 \4 S. Qenddata
calc:
w(1,2)=2;w(1,3)=8;w(1,4)=1;
w(2,3)=6;w(2,5)=1;
6 V! S9 C, d/ j# Lw(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;
w(4,7)=9;
w(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;
# y( a+ [9 L# J2 i+ S% \! E  ?w(8,9)=7;w(8,11)=9;
# _: D$ P' ^  S( g) [: ew(9,10)=1;w(9,11)=2;w(10,11)=4;
@for(roads(i,j):w(i,j)=w(i,j)+w(j,i));
@for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j)));
4 {0 O- O6 D8 Wendcalc
. v) j, f0 \" I; On=@size(cities); !城市的个数;
min=@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)));
@sum(cities(j):x(1,j))=1;
@sum(cities(j):x(j,1))=0; !不能回到顶点1;
( R( X0 ~7 k2 W2 F- E6 [2 e4 n@sum(cities(j):x(j,n))=1;
* B1 c5 j0 w' O@for(roads:@bin(x));
end

/ k- X5 h- V% a9 e- B2 E7 e1 P有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即 从顶点 1 离开后，再不能回到该顶点。

# n4 r8 X5 ~8 e6 a% V求得的最短路径为 1→2→5→6→3→7→10→9→11，最短路径长度为 13。

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

Floyd算法
9 {- D, s  c6 ^7 I. d, Q* b! z/ \2 q


4 O' f8 q, t3 j8 W* [: y8 Z" |
) _5 f$ B+ u2 @7 P
————————————————
5 ]. y0 F" E5 [* F版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785373

. u* C; ~( x1 Z+ i

德古拉

good try~~
$ Y* G2 M- N# j1 q& u- `. s

浅夏110

德古拉 发表于 2020-5-20 08:06
: P1 d* D1 {% Y  |: e: Cgood try~~

浅夏110

德古拉 发表于 2020-5-20 08:06
! |' }- r& A" B5 t7 n8 ugood try~~

& T6 I1 E6 S8 @6 w$ S* |/ L