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

浅夏110

1 两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。
; d& K$ ~# j, s9 ~* Z  G
6 M- ?$ E7 p. e( ]
) v3 q% e6 U+ U7 G+ J# z
2 O3 B" {" E1 L' xDijkstra算法


; e' \/ j: S8 `4 c6 P$ F( h% v例1  某公司在六个城市 中有分公司，从  到  的直接航程票价记在如下矩阵的  位置上。 （∞表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价便宜的路线图。               

- l  h2 b( @4 K) {/ t) w
7 [- P& }5 G9 k2 N
解  用矩阵  （n为顶点个数）存放各边权的邻接矩阵，行向量 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分量

3 i5 e" m) d3 V+ q6 O

7 X3 [" H! N6 S求第一个城市到其它城市的短路径的 Matlab 程序如下：

3 F. U$ w0 k! v2 tclc,clear
. d( l! y, L; ^/ v! c" Ma=zeros(6);
% q+ T* ~& _' C( Q. C; q3 |  V( Q/ qa(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;
a(4,5)=10;a(4,6)=25;
7 V6 d3 O0 j* Q  I# @; ^' xa(5,6)=55;
' ^7 u) ?) z- ?) u5 n/ ca=a+a';
  T0 X1 C: @" ^( d5 h8 m7 Ta(find(a==0))=inf;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
: |3 G) b% o2 N( P( [d(1:length(a))=inf;d(1)=0;temp=1;
while sum(pb)<length(a)
    tb=find(pb==0);
) k$ z* h' S7 C5 P% D) z    d(tb)=min(d(tb),d(temp)+a(temp,tb));
8 K% ]  _' D* r- c5 j    tmpb=find(d(tb)==min(d(tb)));
    temp=tb(tmpb(1));
+ O) p! g! R, }( J5 c    pb(temp)=1;
& E% ^& N( o: O- g6 l9 u    index1=[index1,temp];
# g* M* Y' a$ p& v    temp2=find(d(index1)==d(temp)-a(temp,index1));
4 K  u' H5 ^0 i3 T: h    index2(temp)=index1(temp2(1));
end
d, index1, index2
7 p2 [: }* ~7 |) _1 z0 p  h
2 两个指定顶点之间最短路问题的数学表达式


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


& p: p" v) G. V) }. M' i% T8 k编写 LINGO 程序如下：

* o$ }1 u6 V, J9 D. c5 Ymodel:
% T8 P4 z( g# ~  Asets:
) r* \+ u9 U0 ^1 Z/ Mcities/A,B1,B2,C1,C2,C3,D/;
; V9 x# L% V8 qroads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1,
- O( U# Q8 |) W# H2 r4 C* f; HB2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;
endsets
- F0 p" g( Y7 c" A$ V5 @# sdata:
* E9 f' m5 \7 G9 z9 }/ Gw=2 4 3 3 1 2 3 1 1 3 4;
: h  X. t$ E" }2 ~3 v) z$ Senddata
n=@size(cities); !城市的个数;
min=@sum(roads:w*x);
: O# S) }4 w9 N# z8 V& P6 }@for(cities(i)|i #ne#1 #and# i #ne#n:
    @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;
' d- f$ a0 p& P    @sum(roads(i,j)|j #eq#n:x(i,j))=1;
end

; ]2 A1 o* ]5 [$ J6 z3 A5 a例3 （无向图的最短路问题）

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

0 d  W0 j1 x$ s- Y7 r( A6 Z- `& K

( v- [% d5 u, T: V, \8 f  y编写 LINGO 程序如下：
! K9 w# O' X& q+ S
6 c4 B8 c  _: {) Qmodel:
( Y& V* G3 A0 T3 Osets:
cities/1..11/;
roads(cities,cities):w,x;
endsets
0 d  U/ ?$ C" E. n+ idata:
7 }/ ?) K4 @! K+ w% _8 fw=0;
! v- z4 D. p3 V5 Z' ?enddata
calc:
; J0 [: u7 E4 i/ t5 N, F# Gw(1,2)=2;w(1,3)=8;w(1,4)=1;
6 h) e0 B0 p+ h1 n! q6 g3 @! [- R, Iw(2,3)=6;w(2,5)=1;
w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;
# p' S4 t' |: V5 }; r$ V, Dw(4,7)=9;
w(5,6)=3;w(5,8)=2;w(5,9)=9;
4 {. ^2 k4 Z. `0 w( ^6 Uw(6,7)=4;w(6,9)=6;
. W2 S# S- k, g9 K# d* r4 Lw(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));
@for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j)));
endcalc
n=@size(cities); !城市的个数;
( h9 ]" }. f3 j8 pmin=@sum(roads:w*x);
6 y; i" h& T1 Z& b! |@for(cities(i)|i #ne#1 #and# i #ne#
n:@sum(cities(j):x(i,j))=@sum(cities(j):x(j,i)));
6 _) M5 v& d- a3 ^% p@sum(cities(j):x(1,j))=1;
@sum(cities(j):x(j,1))=0; !不能回到顶点1;
7 P4 L8 C; n  x; Z! w@sum(cities(j):x(j,n))=1;
$ [3 a; `5 y+ B5 ~  v1 v9 P@for(roads:@bin(x));
8 _* j' D( z1 ~4 ^2 Q9 Q/ _end
0 v+ {2 M5 D- b$ C+ ]
有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即 从顶点 1 离开后，再不能回到该顶点。
: o" v5 F2 P3 W
求得的最短路径为 1→2→5→6→3→7→10→9→11，最短路径长度为 13。

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

7 f& i6 y* C9 b5 qFloyd算法


* {3 ^  F2 C4 }. Z5 F' c1 B2 e, i

: |  g. |8 M6 F: S# `4 ~
; n( n% h' i; [4 @) g————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 W/ G8 Z9 y9 c; m& \原文链接：https://blog.csdn.net/qq_29831163/article/details/89785373

' D6 P; b1 J6 V9 @7 `, C" t% d0 G! A
3 Y& G+ K, N1 F% [( R0 e
7 _) L- g- G: p8 x+ \6 {* L
: m2 u$ u! d  q

德古拉

good try~~
- [: ~9 N, F$ ?) {

浅夏110

德古拉 发表于 2020-5-20 08:06
* ?% S  f9 K/ k# Ngood try~~

( n' b" a) `; V8 w, I0 S
' p9 ]; x' P/ h2 n$ S

浅夏110

德古拉 发表于 2020-5-20 08:06
& l7 m5 b7 {$ J2 k; O6 qgood try~~

5 x! D# p4 r$ }( Y, q5 I% ^8 A% A
% Z% W1 Z; t- q! M3 n* y# Z