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

浅夏110

1 两个指定顶点之间的最短路径
5 N6 G' w$ m. _  k- o' @# Z# |问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。
) u; c; ]2 e8 s6 j* L) T
5 E6 t: e$ A) e# i2 x: a: ~3 }
0 l% @$ X, V3 b4 `% K/ A# A) h
; v; t/ y" g& J! q: A, tDijkstra算法


" S. i7 G" O/ O, C例1  某公司在六个城市 中有分公司，从  到  的直接航程票价记在如下矩阵的  位置上。 （∞表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价便宜的路线图。               
% a/ {6 g3 g. p" W9 G
+ |; m; ?$ O* J/ b, D

" g, i3 N1 [4 `% v  C2 s/ s$ t解  用矩阵  （n为顶点个数）存放各边权的邻接矩阵，行向量 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分量
) l+ n+ }: Q! l4 o& Y; v7 k
2 A2 ?* E0 p3 o2 `. N) {

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

clc,clear
a=zeros(6);
: ^4 \$ w. R7 }9 A2 {8 [# b: ka(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;
a(3,4)=10;a(3,5)=20;
" i% T8 d; o$ ua(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';
) h2 E5 X; Y) ia(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;
8 q; s/ S& D& _4 q# z3 S5 ewhile sum(pb)<length(a)
0 J7 r) i& K0 l( t3 x3 J% D    tb=find(pb==0);
8 ]( h( p4 z6 L+ ?1 K    d(tb)=min(d(tb),d(temp)+a(temp,tb));
- ?% U5 g+ O% U% y/ J    tmpb=find(d(tb)==min(d(tb)));
    temp=tb(tmpb(1));
. W( m; }# f4 M9 o    pb(temp)=1;
) k; @- Q5 ^0 t& ^2 m' Y% m6 [    index1=[index1,temp];
& e% S/ f' |% T% J; V% g    temp2=find(d(index1)==d(temp)-a(temp,index1));
    index2(temp)=index1(temp2(1));
end
2 Q% A- c6 [" N+ D) n6 sd, index1, index2
' e  W! O$ b% {; }
. v% I0 y/ N0 z7 o2 两个指定顶点之间最短路问题的数学表达式


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


1 U, e4 u. ~" g/ |% m, ?
编写 LINGO 程序如下：
/ o1 G9 k8 j0 F2 Q( z
2 {: R  W" U* |. d# ^model:
sets:
cities/A,B1,B2,C1,C2,C3,D/;
roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1,
5 |, _( {4 {2 ^+ C4 P, a$ BB2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;
endsets
8 y# [2 l4 T3 h9 f: Ldata:
: w9 M. o) n2 N+ ~* V, S" Lw=2 4 3 3 1 2 3 1 1 3 4;
enddata
n=@size(cities); !城市的个数;
: \. r; y( _  [: L0 n( @min=@sum(roads:w*x);
9 ^, s% U. l! ^8 n9 @% a' J@for(cities(i)|i #ne#1 #and# i #ne#n:
# h$ w  C' ^  S' ^$ g" A8 G    @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));
+ [  u/ O9 K5 Y0 T& }. w    @sum(roads(i,j)|i #eq#1:x(i,j))=1;
+ d& G  w9 v* f    @sum(roads(i,j)|j #eq#n:x(i,j))=1;
end

# w# _& s! D9 e: u% K8 f6 \0 j例3 （无向图的最短路问题）

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

5 m; I- ~* R1 n

: _% @. q* b8 J/ I) I# q编写 LINGO 程序如下：
, K, ^8 I% i# \2 C' z* k. ~
% L& |- a# P5 r) p& r1 ^. Ymodel:
sets:
cities/1..11/;
: {3 q( `+ Z0 ^roads(cities,cities):w,x;
endsets
data:
w=0;
0 b. ~! D6 q6 F+ @. @9 ~enddata
5 I! \1 d) b. ]+ T! i' f5 @+ Lcalc:
2 d, j, v% r7 l6 R% ?w(1,2)=2;w(1,3)=8;w(1,4)=1;
4 @+ K% s+ B2 `0 n6 Ow(2,3)=6;w(2,5)=1;
6 c/ k) \0 N& z3 Nw(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;
7 ^8 v$ [- u" zw(6,7)=4;w(6,9)=6;
% R9 {: o: c+ L5 d* B  ~& mw(7,9)=3;w(7,10)=1;
w(8,9)=7;w(8,11)=9;
w(9,10)=1;w(9,11)=2;w(10,11)=4;
@for(roads(i,j):w(i,j)=w(i,j)+w(j,i));
; {% d. K5 W' b@for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j)));
endcalc
2 U; B' o+ K  Kn=@size(cities); !城市的个数;
/ ]' E# H  y7 G+ Qmin=@sum(roads:w*x);
/ D( c# G/ @+ l: N7 _@for(cities(i)|i #ne#1 #and# i #ne#
% B1 R- {( F0 X8 on:@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;
@sum(cities(j):x(j,n))=1;
* U3 ]- q6 U1 Z0 a! h+ P" W@for(roads:@bin(x));
end

" d4 V: k& M  q: ^有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即 从顶点 1 离开后，再不能回到该顶点。
3 `( D; U; V) m1 n; c. Q1 X
) O* \* t$ o3 f2 J" u; i; @求得的最短路径为 1→2→5→6→3→7→10→9→11，最短路径长度为 13。
7 w- v+ f  Q1 q6 k; j
3 每对顶点之间的最短路径
: ~" F! Y% s0 m" s6 z计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。具体方法是： 每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反 复执行 n −1次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法 的时间复杂度为  。第二种解决这一问题的方法是由 Floyd R W 提出的算法，称 之为 Floyd 算法。

Floyd算法
: N( \  j0 i( J$ S" }5 ?% z" {

9 ?" Z* o" T, n2 W1 p# e! k
+ F% W& E5 t9 j$ @% p$ V

) V; u7 W2 `6 j( h0 O! k9 V6 G————————————————
4 @: {% {6 g8 _# \版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785373

德古拉

good try~~
+ v8 i' F% Y! X

浅夏110

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

% I( V+ b$ `/ T& R2 {3 w( a+ c

浅夏110

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

9 L1 m7 Z) x" M0 l1 [8 \; J: `
0 @  l% ]3 d# h; G' X: F; k