运筹学05_图与网络分析2-最短路888

最短路问题最短(通)路问题是最重要 的优化问题之一，例如各种管道 的铺设、线路的安排、厂区的布 局、设备的更新及运输网络的最 小费用流等。(最短距离、费时 最少、费用最省)

2

1

3

2

5

20 1 8

6

5 1 2 9

3 6 4 6

9

72

9

7 7 1

11 1

13

3 1

4 10

9

2

1

3

2

5

20 1 8

6

5 1 2 9

3 6 4 6

9

72

9

7 7 1

11 1

13

3 1

4 10

9

一般的最短路问题描述：给定一个赋权有向图D=(V,A),对每一个弧a=(vi,vj),相应 地有权w(a)=wij,又给定D中的任何两个顶点vs和vt ,设P是 从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P), 最短路问题就是要在所有从vs到vt的路中，求一条权最小的路， 即一条从vs到vt的路P0使得：

(P0 ) min (P)P

路P0的权称为从vs到vt的距离，记为d(vs,vt)。

求网络上的一点到其它点 的最短路 Dinkstra标号法

这是解决网络中某一点到其它点的最 短路问题时目前认为的最好方法。 适用于有向图权值非负的情况

有向图权值非负---- Dijkstra算法

Dijkstra算法的基本步骤(权值非负) 1、给顶点v1标号(0),v1称为已标号点，记标号点集为 V1={v1} 2、在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连 (并且以vi为起点)的点vj, 3、在第2步选出的点中，选出满足下面条件的点vk,并给vk标 号(l,L1k),其中l为第一标号， L1k为第二标号 L1k L1l ωlk min L1i ωij vi V1 ,v j V2

为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk 相邻的点是vl 4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则 从vn开始，按照第一个标号逆向追踪，直到v1,就得到从v1到 vn的最短路，vn的第二个标号表示最短路的长度。

木器厂有六个车间，办事员经常要到各个车间了解生产 进度。从办公室到各车间的路线由图1给出。找出点1 (办公室)到其它各点(车间)的最短路

222 5 1

7

13

35

5 3

51

57

7

4

6

2

225

权wij(dij)距离、价格

1

3

点(vi)

边eij或记为(vi,vj)

20

①从点1出发，因L11=0, 在点1处标记 0

2

2 5 1

7

13

35

5 3

51

57

7

4

6

20

从已标号的点出发，找与这些 相邻点最小权数(距离)者，找 到之后：标号；边变红。

2

2 5 1

7

13

35

5 3

51

57

7

4

6

(1,2)

20

2

2 5 1

7

13

35

5 3

51

57

7

4

6

(1,2)

0

2

251

③从已标号的点出发，找与这 些相邻点最小权数(距离)者， 找到之后：标号；边变红。

2

7

13

35

5 3

51

57

7

4

6

(1,2)

0

2

2513

③从已标号的点出发，找与这 些相邻点最小权数(距离)者， 找到之后：标号；边变红。

2

13

7

35

5 3

51

57

7

4

6

(1,2)

④重复上述

步骤，直至全部的 点都标完。

0

2

225 1

13(1,3)

7

35

5 3

51

57

7

4

6

(1,2)

④重复上述步骤，直至全部的 点都标完。

0

2

225 1

13(1,3)

35

4

75 3

51

57

7

4

6

(1,2)

④重复上述步骤，直至全部的 点都标完。

0

2

225 1(2,4)

13(1,3)

75 3

3(4,4)

51

57

7

4

5

6

(1,2)

④重复上述步骤，直至全部的 点都标完。

0

2

225 1(2,4)

13(1,3)

75 3

35

517

57

7

4

6

(1,2)

0

2

225 1(2,4)

13(1,3)

75 3

35

51

57

7

4

6

(3,7)

(1,2)

0

2

225 1(2,4)

13(1,3)

75 3

35

8

51

57

7

4

6

(3,7)

本文来源：https://www.bwwdw.com/article/147i.html