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

1、最短路问题 最短（通）路问题是最重要的优化问题之一，例如各种管道的铺设、线路的安排、厂区的布局、设备的更新及运输网络的最小费用流等。（最短距离、费时最少、费用最省）,破圈法是：任取一圈，去掉圈中最长边，直到无圈 避圈法是：去掉图中所有边，从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边） 一个连通的无向图叫做树 树 无圈，但不相邻的两个点之间加一条边，得到一个圈 树 中任意两个顶点之间，恰有且仅有一条链,下图中右图是支撑树,一个连通图能一笔画的条件是： 它没有奇点；或者它恰好有一个奇点。,一个图有5个点，条边。这个图一定是 A连通图 B树 C完全图 D不连通图,连通图G有n个点，其

2、部分树是T，则有 A.T有n个点n条边 B.T的长度等于G的每条边的长度之和 C.T有n个点n1条边 D.T有n1个点n条边,某人要从上海乘飞机到奥地利首都维也纳，他希望选择一条航线，经过转机，使他在空中飞行的时间尽可能短。该问题可转化为 A.最短路线问题求解 B.最大流量问题求解 C.最小树问题求解 D.中国邮递员问题求,10,9,6,3,1,7,0,2,11,5,13,2,8,6,1,7,2,2,2,9,1,5,1,1,9,1,4,3,9,7,4,6,3,10,9,6,3,1,7,0,2,11,5,13,2,8,6,1,7,2,2,2,9,1,5,1,1,9,1,4,3,9,7,4,6,3

3、,一般的最短路问题描述：,给定一个赋权有向图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的权称为从vs到vt的距离，记为d(vs,vt)。,Dinkstra标号法,这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。 适用于有向图权值非负的情况,求网络上的一点到其它点的最短路,有向图权值非负- Dijkstra算法,Dijkstra算法的基本步骤（权值

4、非负） 1、给顶点v1标号（0），v1称为已标号点，记标号点集为V1=v1 2、在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连（并且以vi为起点）的点vj， 3、在第2步选出的点中，选出满足下面条件的点vk，并给vk标号（l,L1k），其中l为第一标号， L1k为第二标号,为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk 相邻的点是vl,4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则 从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到 vn的最短路，vn的第二个标号表示最短路的长度。,5,1,2,7,5,6,3,4,2,5,5,2,7,3,

5、1,3,5,7,1,木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。找出点1（办公室）到其它各点（车间）的最短路,距离、价格,边eij或记为（vi，vj）,点（vi）,权wij(dij),0,从点1出发，因L11=0，在点1处标记,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,(1,2)

6、,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。,(1,2),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。,3,(1,2),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,(1,3),(1,2),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。

7、,4,(1,2),(1,3),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,(2,4),(1,3),(1,2),(4,4),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,7,(1,3),(1,2),(2,4),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,(3,7),(1,3),(1,2),(2,4),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,8,(1,3),(1,2),(2,4),(

8、3,7),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,(6,8),(1,3),(1,2),(2,4),(3,7),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,(1,3),(1,2),(2,4),(3,7),(6,8),(5,13),5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,(1,2),(1,3),(2,4),(3,7),(6,8),(5,13),对有向图同样可以用标号算法： 例2 如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。,v1,v9,v8,v7,v6,v

9、5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,1，4,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,1，4,v1,v9,v

10、8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,1，4,2，5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,1，4,2，5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,1，4,2，6,2，6,2，5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,1，3,2，5,1，4,2，6,2，6,v1,v9,v8,v7,v6,

11、v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,6，7,2，6,1，3,2，5,1，4,2，6,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,2，6,6，7,2，6,6，8.5,1，3,1，4,2，5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,6，7,2，6,6，8.5,7，9,1，3,2，6,2，5,1，4,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0

12、,1，3,2，6,2，6,2，5,6，7,1，4,7，9,6，8.5,练习：求从v1到v8的最短路,(0),(1,1),(1,3),(3,5),(2,6),(5,10),(5,9),(5,12),Dijkstra算法的不足,Dijkstra算法仅适合于所有的权lij0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。 根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从v1到v2的最短路是(v1, v3, v2)，权是-1。,v1,v3,v2,2,2,-3,无向图,将边vi，vj看作两条弧， (vi, vj)和(vj, vi),二、最短路的矩阵算法 首先写出

13、弧长矩阵D 第一步：划去矩阵D中第一列，并给第一行以标号0。,第二步：在已标号中未划去的元素中，寻找出最小的元素aij并圈起来，此时把第j列划去，同时给第j行标号i。并把第j行中未划去的各元素都加上aij。 第三步：如果各行均已获得标号，则停止，并利用标号倒向追踪，得到v1到各点的最短路。 若存在未标号行，返回第二步。,例 求v1到各点vj的最短路。,v1,v4,v2,v5,v3,v6,1,2,5,3,2,4,2,3,2,4,4,1,2,v1 v2 v3 v4 v5 v6 v1 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2

14、 v3 v4 v5 v6 0 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 3+1 4+1 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v

15、4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 4+2 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0

16、1 2 1 0 4 5 v3 2 0 5 1 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 1 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 1+4 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2

17、0 5 5 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 5 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 6

18、2 2 ,v1到各点vj的最短路。,v1,v4,v2,v5,v3,v6,1,3,1,2,例4：企业要制定一台重要设备更新的五年计划，目标是使总费用（购置费用和维修费用之和）为最小。此设备在各年初价格及使用期中所需维修数据如下：,v1,v2,v3,v4,v5,v6,16,22,18,17,17,16,30,41,59,31,23,41,30,22,23,解：用点vi表示年初。（i=1,2,6）， v6表示第五年底。弧aij=（vi，vj）表示第i年初购置设备使用到第j年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从v1到v6的一条最短路。,v1,v2,v3,v4,v5,v6,16,22,18,17,