数模往届图论最短路问题

最短路问题一、固定起点的最短路二、任意两点的最短路三、最短路算法的应用定义

(1)设P(u,v)是赋权图G

中从u到v的路径，则称w(P)=

w(e)为路径P

的权．e˛

E

(

P

)(2)

在赋权图G

中，从顶点u

到顶点v

的具有最小权的路P*

(u,v)，称为u

到v

的最短路．最短路问题（SPP－shortest

path

problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。一、固定起点的最短路最短路问题是网络理论中应用最广的问题之一。许多优化问题可以使这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。问题：无向连通简单带权图，求出顶点a与z之间的最短通路的长度。算法思想：最短路是一条路径，且最短路的任一段也是最短路．求出从a到第一个顶点的最短通路的长度，从a到第二个顶点的最短通路的长度，依次类推，直到求出从a到z的最短通路的长度为止。即类似于树生长的过程。算法细节（Dijkstra，迪克斯特拉算法）：（1）初始标记：用记号L0

(a)=0

和L0

(v)=¥

分别表示在没发生任何迭代之前从

a

到这些顶点之间的最短通路的长度（0

表示第

0

次迭代），S0

=

f

,

其中这些通路只包含顶点

a（因为不存在从a

到除a

外顶点的通路，所以¥

是a

与这样的顶点之间的最短路的长度）。（2）通过形成特殊顶点的集合完成算法。Sk

表示标记过程中第k

次迭代之后的特殊顶点的集合。集合Sk是把不属于

Sk

-1

的带最小标记的顶点

u

添加到

Sk

-1

里来形成的，即Sk

=

Sk

-1

+u（3）更新v

的标记（

v

ˇ

Sk

）。从a

到v的只包含Sk

中顶点的最短通路，或者是从a

到

v

的只包含Sk

-1

中顶点（即不包括u

在内的特殊顶点）的最短通路，或者是在第k-1

阶段从a

到u

的最短通路加上边（u，v）。即：Lk(v

)=min{Lk

-1(v

),Lk

-1(u

)+w(u

,v

)}其中，Sk

=Sk

-1

+u（4）重复（2）、（3）。整个过程中，每次添加一个顶点到特殊顶点的集合里，直到添加到z

为止。Dijkstra

算法：求G

中从顶点u0

到其余顶点的最短路设G

为赋权有向图或无向图，G

边上的权均非负．对每个顶点，定义两个标记（

l(v)，z(v)），其中:l(v)：表从顶点u0

到v

的一条路的权．z(v)：v

的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终l(v)为从顶点u0到v

的最短路的权．S：具有永久标号的顶点集输入:G

的带权邻接矩阵w(u,v)算法步骤：u

‹v

*（4）

若

S

„

φ，转

2，否则，停止.用上述算法求出的l(v)就是u0

到v

的最短路的权，从v

的父亲标记z(v)

追溯到u0

,

就得到u0

到v

的最短路的路线.（１）赋初值：令

S＝{

u0

},

l(u0

)

=0"v

˛

S

=V

\S

,令l(v)=W

(u0,v),z(v)=u0u

‹u0更新

l(v)

、

z(v)

：

"

v

˛

S

=

V

\

S

,若

l(v)

>

l(u)

+

W

(u,

v)则令l(v)

=

l(u)

+

W

(u,

v)

,

z(v)

=

u设v

*

是使l(v)取最小值的S

中的顶点，则令S=S∪{v

*

}，例

1

求下图从顶点

u1

到其余顶点的最短路．¥0

6

3

0

409051203¥218¥¥¥¥

0¥61¥¥¥

07¥¥9¥

0先写出带权邻接矩阵：

W

=因G

是无向图，故W

是对称阵．TO

MATLAB(road1)u1u2u5u7u8218

u41u3

9651u63697243第0步u2u5u6u8218

u4152997631

6

432(u1)8(u1)∞∞∞u7∞u1第1步uu331(u1)u5u6u8218

u4152997631

6

432(u1)8(u1)∞∞∞u1第2步uu331(u1)u710(∞u1,u3)uu22u6u8218

u4152997631

6

432(u1)8(u1)∞∞u1第3步uu331(u1)u710(u1,u3)uu223(u∞1,u2)uu55193934

6

2(u1)u1第4步uu331(u1)u710(u1,u3)uu223(u∞1,u2)28

u4651uu668(u1)1726∞(u1,u2,

5u

)u8

∞12(u1,u2,u5)uu5519393

6

2(u1)u1第5步uu331(u1)u710(u1,u3)uu223(u1,u2)45u

)u8

12(u1,u2,u5)uu5528

uu44651uu6678(u(u1,1u)12,u5,u6)726(u1,u2,2115293963162(u1)u1第6步uu331(u1)uu223(u1,u2)uu66456(u1,u2,

u

)12(u1,u2,u5)uu5517(u

,u2,u5,u6)78

uu44791(0u(1u,u1,2u,u3)5,u6,u4)uu7uu887u1uu33u2uu66u5uu44uu7u81243553317284例2

求出点1到其余各顶点的最短有向路的长度？

Dijkstra算法:P

={1},T

={2,3,4,5},且S1

=0,S2

=w

<1,2

>=5S3

=

w

<1,3

>=

¥,

S4

=

w

<1,4

>=

3,

S5

=

w

<1,5

>=

¥k

=

4,

P

={1,4},T

={2,3,5}S2=

min{

S2

,

S4

+

w

<

4,2

>}

=

min{

5,3

+¥}

=

5S3

=

min{

S3

,

S4

+

w

<

4,3

>}

=

min{

¥,3

+

7}

=10S5

=

min{

S5

,

S4

+

w

<

4,5

>}

=

min{

¥,3

+8}

=11k

=

2,

P={1,4,2},T

={3,5}S3

=

min{

S3

,

S2

+

w

<

2,3

>}

=

min{

10,5

+

3}

=

8S5

=

min{

S

5,

S2

+

w

<

2,5

>}

=

min{

11,5

+¥}

=11k

=

3,

P

={1,4,2,3},T

={5}S5

=

min{

S5

,

S3

+

w

<

3,5

>}

=

min{

11,8

+1}

=

9显然:S1

=0,S2

=5,S3

=8,S4

=3,S5

=9例3

狼、羊、白菜问题狼、羊、白菜过河问题猎人要把一只狼、一头羊和一篮白菜从河的左岸带到右岸，但他的渡船太小，一次只能带一样。因为狼要吃羊，羊会吃

白菜，所以狼和羊，羊和白菜不能在无人监视的情况下相处。问猎人怎样才能达到目的？人、狼、羊、菜四种的任意组合共有16种。其中狼羊菜、狼羊、羊菜三种不允许出现，所以人、人狼、人菜也不允许出现。因此，允许出现的情况共有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空。把这10种状态视为10个点，若一种状态通过一次摆渡后可变为另一种状态，则在两种状态（点）之间画一直线，得示意图如下：0

4

2

4

671353将各顶点到“人狼羊菜”的距离标在图中各顶点处，可知有两种最迅速最安全的渡河方案：人狼羊菜→狼菜→人狼菜→狼→人狼羊→羊→人羊→空；人狼羊菜→狼菜→人狼菜→菜→人羊菜→羊→人羊→空；每种方案都要七次。这种“用顶点代表状态，边代表状态间的转移”的状态转移图模型颇具代表性．任何具有有限

个状态的多步决策问题都可以类似地建立图的

模型，利用图论工具来解决．这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路。二、任意两点间的最短路问题直接在图的带权邻接矩阵中用插入顶点的方法依次构造出n

个矩阵

D(1)、

D(2)、…

、D(

n

)，使最后得到的矩阵

D(n

)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径．算法原理——

求距离矩阵的方法ij

n·n把带权邻接矩阵W

作为距离矩阵的初值，即D(0)=(d

(0))=Wij

n·nij（１）D(1)=

(d

(1))

，其中d

(1)=

min{d

(0)

,

d

(0)

+

d

(0)

}ij

i1 1

jijd

(1)是从vi

到vj

的只允许以v1

作为中间点的路径中最短路的长度．ij

n·nij（2）D(2)=

(d

(2))

，其中d

(2)=

min{d

(1)

,

d

(1)

+

d

(1)

}ij i

2 2

jd

(2)是从vi

到vj

的只允许以v1

、v2

作为中间点的路径中最短路的长度．ij…(

)(n

)ij

n·n（n

）D

n

=

(dij

ij)

，其中d

(n

)in

nj=

min{d

(n

-1)

,

d

(n

-1)

+

d

(n

-1)

}(n

)ijd、

、n是从

vi

到

vj

的只允许以

v1

v2

…、v

作为中间点的路径中最短路的长度．即是从vi

到vj

中间可插入任何顶点的路径中最短路的长，因此D(n

)即是距离矩阵．ij

n·nij=

(r

(0)

)

,

=

jR

(0)

r

(0)每求得一个D(k)时，按下列方式产生相应的新的R(k)ik

kj否则ij

ij(k

)若d

(k

-1)

>

d

(k

-1)

+

d

(k

-1)=

r

(k

-1)krij算法原理——

求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．R=(rij

)n·n

,rij

的含义是从vi

到vj

的最短路要经过点号为rij

的点．即当vk

被插入任何两点间的最短路径时，被记录在R(k

)中，依次求D(n

)的同时求得的R(n

)，可由R(n

)来查找任何点对之间最短路的路径．ij算法原理——

查找最短路路径的方法ij

1若r

(n

)=p

，则点p1

是点i

到点j

的最短路的中间点.然后用同样的方法再分头查找．若：k（１）向点

i

追朔得：

r

(n

)

=

p

,

r

(n

)

=

p

,…,

r

(n

)

=

pip1

2

ip2

3

ipk（２）向点

j

追朔得：

r

(n

)

=

q

,

r

(n

)

=

q

,…,

r

(n

)

=

jp1

j

1

q1

j

2

qm

jpkp3

p2

p1q1q2qm则由点i到j的最短路的路径为：i,

pk

,,

p2

,

p1,

q1

,

q2

,,

qm

,

j算法步骤Floyd

算法：求任意两点间的最短路．D(i,j)：i

到

j

的距离．R(i,j)：i到

j之间的插入点．输入:

带权邻接矩阵

w(i,j)赋初值：对所有i,j,d(i,j)‹w(i,j),r(i,j)‹j,k

‹1更新d(i,j),r(i,j)对所有i,j，若d(i,k)+d(k,j)<d(i,j)，则d(i,j)

‹

d(i,k)+d(k,j),r(i,j)

‹

k若k=n

，停止．否则k

‹k+1，转(2)．例求下图中加权图的任意两点间的距离与路径．v1v4v3v593v27422第0步D

(0

)R

(

0)

97

15

5

1

2

3

4 5

2

3

4=

1

2

3

42

3

42

3

4

3

15

¥0

15

¥

0

9

¥

3

¥

0

2

¥

=

¥

2

0

2

4

,¥

2

07

4

¥4272D

(1

)R

(1

)

97

15

¥5

1

2

3

4 5

2

3=

1

2

3

43

43

4

3

15

¥¥0

15

¥插入v1

得：

0

9

¥

3

¥

0

2

=

¥

2

0

2

4

,2

04

¥121211第2步351514D

(2

)R

(

2

)¥¥

1

2

42

3

12

3

41

3

42

3

97

15

5

=

¥

1¥插入v2

得：

0

9

30

2 1

22

0

2

4

,

3 1

2

2

07

40

5

¥

¥111116

1619

192=

22

222D

(3

)R

(

3

)插入v3

得：

0

96

13

5

1

2

2

4

3

2

3

3=

2

2

3

43

3

43

3

3

36

13

9 1

1

3

15

0

2

4

=

1

1

2

0

2

4

,4

2

0

15

6

4

60

35

第3步D

(4

)R

(

4

)插入v4

得：

0

76

43

5

7

5

3

9

0

2

4

=

5

2

0

2 4

,4

2

06

4

6

1

4

4

4

4

2

3

3=

4

2

3

43

3

43

3

3

36

13

90

45

D

(5

)

=

D

(

4)

,第4步R

(5

)

=

R

(

4

)TO

MATLAB(road2(floyd))d51

=9

，故从v5

到v1

的最短路为９．r51

＝４．由

v4

向

v5

追朔：

r54

=

3,

r53

=

3

;由v4

向v1

追朔：r41

=1所以从v5

到v1

的最短路径为：5

fi

3

fi4

fi

1.建模实例

最优截断切割问题1997B奥运会临时超市网点设计2004B例1

某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。年份12345购置费1820212324使用年数0~11~22~33~44~5维修费57121825三、最短路应用年份12345购置费1820212324使用年数0~11~22~33~44~5维修费5712182528v1v2v3v62325262930856042324462v433v54535选址问题--中心问题选址问题是指为一个或几个服务设施在一定区域内选定它的位置，使某一指标达到最优值．选址问题的数学模型依赖于设施可能的区域和评判位置优劣的标准，有许多不同类型的选址问题．在此只简单介绍服务设施与服务对象都位于一个图的顶点上的单服务设施为题．中心问题：有些公共服务设施（例如一些紧急服务型设施如急救中心、消防站等）的选址，要求网络最远的被服务点离服务设施的距离尽可能小．例2

某城市要建立一个消防站，为该市所属的七个区服务，如图所示．问应设在那个区，才能使它至最