图论-4(最短路问题).ppt

1、第七章 图论,引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图,7.4 最短路问题,一、问题的提出,赋权图（网络）： G=(V, E) 中，给每条边 a= 赋予一个非负实数权 wij ，得到一个有向网络,7.4 最短路问题,路径 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和,距离矩阵 对上述网络，定义 D=(dij)nn，n=|V| wij 当 E dij = 其它 带权路径长度 对上述网络，路径 v1,

2、v2 , ,vk 的带权路径长度定义为,7.4 最短路问题,最短路问题在实际工作中应用,1、通讯网络中最可靠问题 2、最大容量问题 3、统筹方法中求关键路线 4、背包问题 5、选址问题 6、工件加工顺序问题 7、中国邮递员问题,背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。,7.4 最短路问题,例,一位旅客要从A城到B城 他希望选择一条途中中转次数最少的路线； 他希望选择一条途中所花时间最短的路线

3、； 他希望选择一条途中费用最小的路线；,这些问题均是带权图上的最短路径问题。,边上的权表示一站 边上的权代表距离 边的权代表费用,7.4 最短路问题,Dijkstra算法 Floyd算法 Floyd-Warshall算法,7.4 最短路问题,Dijkstra算法,Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。 荷兰计算机科学教授Edsger W.Dijkstra(1930-) 在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。

4、 Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路。边(i,j)的权(i,j)0，且结点x的标号为L(x)。结束时，L(z)是从a到z的最短长度。 举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。,7.4 .1 Dijkstra算法,Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。 第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最

5、短路径长度。 按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。,7.4 .1 Dijkstra算法,设源点为v0 初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点） 然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）： 若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值

6、vm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，。 如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。,7.4 .1 Dijkstra算法,procedure Dijkstra(G:所有权都为正数的加权连通简单图) G带有顶点av0,v1,vnz和权(vi,vj)，若(vi,vj)不是G的边，则(vi,vj) for i:1 to n L(vi) L(a):0 S: （初始化标记，a的标记为0，其余结点标记为，S是空集 while z

7、 S begin u:不属于S的L(u)最小的一个顶点 S:Su for 所有不属于S的顶点v if L(u)(u,v)L(v) then L(v):L(u)(u,v) 这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记 endL(z)从a到z的最短长度,dij,7.4 .1 Dijkstra算法,下面给出该算法的框图：,通过框图，容易计算该算法计算量 。,7.4 .1 Dijkstra算法,下面通过一个实例来说明Dijkstra算法是如何工作的。,7.4 .1 Dijkstra算法,7.4 .1 Dijkstra算法,1,用Dijkstra算法求a和z之间最短路所用的步骤。,7.4

8、 .1 Dijkstra算法,Dijkstra算法(另外一种说明),求有向网络 G=(V, A) 中结点v1 到其它结点的最短距离。 设D为G的距离矩阵，n=|V|，向量U=(u1, u2, , un)的ui 标记结点v1到vi 的距离。 S为已取得最短路的结点集合，其中每个结点在U中有固定标号标记取得的最短路的长度；S为未取得最短路的结点集合，其中每个结点在U中有临时标号。,7.4 .1 Dijkstra算法,0. 初始化：u1(1) 0，uj(1) d1j ( j =2,3,n) S(1) v1，S(1) v2 , v3 , , vn，m=1; 1. 选固定标号：在S(m)中求vk，使得

9、uk(m) =minuj(m) | vjS(m)。 若 uk(m) =，则S(m)中的结点无最短路径；否则转2。 2. 判结束：令 S(m+1) S(m) vk, S(m+1) S(m) vk 若 m = n1，结束。 3. 修改临时标号：对所有vjS(m+1) ，令 uj(m+1) =minuj(m) , uk(m)+dkj，m m+1；转1。,7.4 .1 Dijkstra算法,Dijkstra算法只求出图中一个特定的顶点到其他各定点的最短路。但在许多实际问题中，需求出任意两点之间的最短路，如全国各城市之间最短的航线，选址问题等。当然，要求出一个图的任意两点间的最短距路，只需将图中每一个顶

10、点依次视为始点，然后用Dijkstra算法就可以了。 Dijkstra算法在物流配送中的应用 OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。,7.4 .1 Dijkstra算法,Dijkstra算法要求图上的权是非负数，否则结果不正确； Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。 利用求最短路的方法求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，必须采用Floyd算法-动态规划算法 Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间

11、的最短路径矩阵.,7.4.2 Floyd算法,如果有一个矩阵D=d(ij)，其中d(ij)0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。 【分析】 对于任何一个城市而言，i 到 j 的最短距离不外乎存在经过 i 与 j 之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是城市的数目)，检查d(ij)与d(ik)+d(kj)的值；d(ik)与d(kj)分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离，因此d(ik)+d(kj)就是 i 到 j 经过k的最短距离。所

12、以，若有d(ij)d(ik)+d(kj)，就表示从 i 出发经过 k 再到j的距离要比原来的 i 到 j 距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的 i 到 j 的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是 i 到 j 之间的最短距离了。,7.4.2 Floyd算法,定义7.4.1:已知矩阵A(aij)ml，B(bjk)ln，规定CA*B(cij)mn，其中cijmin(ai1b1j, ai2b2j, , ailblj) 定义7.4.2已知矩阵A(aij)mn，B(bij)mn，规定DA B(dij)mn，其

13、中dijmin(aij,bij) 可以利用上面定义的运算求任意两点间的最短距离。 已知n阶加权简单图G，设D(dij)mn 是图G的边权矩阵，即dij(i,j)(若G是有向图，则dij),若结点i到结点 j无边相连时，则取dij。然后依次计算出矩阵D2, D3, Dn及S,7.4.2 Floyd算法,其中 D2D*D( )nn d(2)ij=mindi1+d1j，di2+d2j，dindnj d(2)ij表示从vi出发两步可以到达vi的道路中距离最短者。 D3D2*D( )nn d(k)ij表示从vi出发k步可以到达vj的道路中距离最短者 DnDn-1*D( )nn SD D2 D3 Dn(S

14、ij)nn 由定义可知dijk表示从结点i到j经k边的路（在有向图中即为有向路）中的长度最短者，而Sij为结点i到j的所有路（若是有向图即为有向路）中的长度最短者。 Floyd算法的时间复杂性是O(n4)。,7.4.2 Floyd算法,求下图各点间的最短路径,7.4.2 Floyd算法,解：,D(2), 1 2 1 3 7 1 2 3 6 , 1 2 1 3 7 1 2 3 6 ,*, 2 3 4 8 2 3 6 4 ,7.4.2 Floyd算法,类似可得：, 3 4 6 5 ,D(3),D(5),D(4), 6 , ,7.4.2 Floyd算法,所以：,SD D(2) D(3) D(4) D

15、(5)(sij)66,7.4.3 Floyd-Warshall算法,Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。 基本思想： 通过求解矩阵序列D(0)，D(1)，D(n)来实现问题的求解。,7.4.3 Floyd-Warshall算法,其中： D(0)图的距离矩阵； D(n)最终解； dij边(vi,vj)的权值 d(k)ij从vi到vj在所经过的顶点号k最短路径长度。 即通过依次比较顶点修改路径实现求解的。 对于任意两个顶点vi，vj，对于新比较的顶点vk一旦出现d(k-1)ijdikdkj，则修改对应的d(k)ij。,7.4.3 Floyd-Warshall算法,

16、例：求下图各点间的最短路径,7.4.3 Floyd-Warshall算法,解：比较经过顶点号1的矩阵,D(1), 1 2 1 3 7 1 2 3 6 ,1 2 3 4 5 6,1 2 3 4 5 6,无改变,7.4.3 Floyd-Warshall算法,解：比较经过顶点号2的矩阵,D(2), 1 2 1 3 7 1 2 3 6 ,1 2 3 4 5 6,1 2 3 4 5 6,4,8,d(1)14d12d24 所以修改d(2)14,d(1)16d12d26 所以修改d(2)16,7.4.3 Floyd-Warshall算法,解：比较经过顶点号3的矩阵,D(3), 1 2 4 8 1 3 7 1

17、 2 3 6 ,1 2 3 4 5 6,1 2 3 4 5 6,4,2,3,3,d(2)14d13d34,d(2)15d13d35,d(2)24d23d34,d(2)25d23d35,7.4.3 Floyd-Warshall算法,解：比较经过顶点号4的矩阵,D(4), 1 2 2 4 8 1 2 3 7 1 2 3 6 ,1 2 3 4 5 6,1 2 3 4 5 6,6,5,4,d(3)16d13d34d46,d(3)26d23d34d46,d(3)36d34d46,7.4.3 Floyd-Warshall算法,解：比较经过顶点号5的矩阵,D(5), 1 2 3 4 6 1 2 3 5 1 2 4 3 6 ,1 2 3 4 5 6,1 2 3 4 5 6,无改变,7.4.3 Floyd-Warshall算法,解：比较经过顶点号6的矩阵,D(6), 1 2 3 4 6 1 2