资源描述
,Click to edit Master title style,Click to edit Master text styles,图论及其应用,*,最短路径问题,(,Shortest Path Problem,),1,最短路径问题(Shortest Path Problem),最短路径问题,所谓,最短路径问题,(,Shortest Path Problem,)就是在一个带权图中找出两点之间的最短路径(权和最小的路径)。,最短路径问题通常有如下几种类型:,(,1,)带权(非负权)图中两个指定点之间的最短路径;,(,2,)带权图(非负权)中任意两点间的最短路径;,(,3,)带权图(非负权)中从一个指定点到其它所有点的最短路径;,(,4,)带权图(非负权)中必须通过指定点的两个指定点之间的最短路径;,(,5,)带权图(任意权)中最短路径问题,等等。,2,最短路径问题 所谓最短路径问题(Shortest Pa,两个指定点之间的最短路径问题,求解方法一,:,回溯法,(,从终点开始逐步逆向推算,),主要步骤:,先看与终点连接的结点,在结点上方写上该结点到终点的最短路线及权值;,再将每个结点(与终点连接的结点)看成新的终点,以此类推,一直到起点为止。若在这过程中,一个结点同时与多个不同终点相连接,则该结点上方写上该结点到这些终点中最短的路线及权值;,最终,起点上方的最短路线及权值即为起点到终点的最短路线及长度。,3,两个指定点之间的最短路径问题求解方法一:回溯法(从终点开始逐,例,使用回溯法求下图中结点,1,到结点,10,的最短路径,300,6-9-10,150,8-10,100,9-10,400,5-8-10,275,7-8-10,600,2-6-9-10,500,4-6-9-10,600,3-5-8-10,650,1-4-6-9-10,4,例 使用回溯法求下图中结点1到结点10的最短路径3006-9,练习,城市,A,到城市,B,的交通道路如下图所示,线上标注的数字为两点间距离,(,单位:万米,),。某公司现需从,A,市紧急运送一批货物到,B,市。假设各条线路的交通状况相同,请为该公司寻求一条最佳路线。,3,7-B,6,8-B,8,4-7-B,9,5-7-B,10,6-8-B,16,1-5-7-B,17,2-5-7-B,13,1-6-8-B,18,A-1-5-7-B,5,练习 城市A到城市B的交通道路如下图所示,线上标注的数字为两,指定点到其它所有点的最短路径,解决这一问题最著名的方法是,Dijkstra,算法,,这个算法是由荷兰计算机科学教授,Edsger W.Dijkstra,在,1959,年提出的。,他在,1972,年获得美国计算机协会授予的,图灵奖,,这是计算机科学中最具声望的奖项之一。,6,指定点到其它所有点的最短路径解决这一问题最著名的方法是Dij,Dijkstra,算法,Dijkstra,算法,是由近及远地逐渐找出源点到其它任一点的最短路径。,假设,G=,是一个连通带权简单图,,G,中顶点为,v0,v1,.,vn,,假设,v0,为起点,边,(,vi,vj,),(或,)的权记为,w,ij,,若,(,vi,vj,),(或,)不是图中的边,则权为,w,ij,=,,标号,l(x),表示从,v0,到,x,的最短路径的长度。,则,Dijkstra,算法原理如下:,7,Dijkstra算法 Dijkstra算法是由,Dijkstra,算法的伪代码,Procedure Dijkstra(G,W,a(,z,),begin,for i:=1 to n do l(vi):=,l(a):=0,S:=;/,初始化标号及,S,,,S,用于保存已考察过的,顶点的序列,while V(G)-S,(,z,S,),do,begin,u:=,不属于,S,且,l(u),最小的一个顶点,;,if u,为顶点,z,S:=Su,;,else,S:=Su,;,for,所有不属于,S,的顶点,v do l(v):=minl(v),l(u)+w,uv,;,end,end Dijkstra,8,Dijkstra算法的伪代码Procedure Dijkst,例,用,Dijkstra,算法求下图中,从,a,到所有其它结点的最短路径及长度。,9,例 用Dijkstra算法求下图中从a到所有其它结点的最短路,步骤,u S,a b c d e z,0,-,0,1,a,a,0,4 2 ,2,c,a,c,0,3 2 10 12 ,3,b,a,c,b,0,3 2 8 12 ,4,d,a,c,b,d,0,3 2 8 10 14,5,e,a,c,b,d,e,0,3 2 8 10 13,6,z,a,c,b,d,e,z,0,3 2 8 10 13,l(v):=minl(v),l(u)+w,uv,10,步骤 u S,例,用,Dijkstra,算法求下图中,从,A,到其它所有结点的最短路径及长度,11,例 用Dijkstra算法求下图中从A到其它所有结点的最短路,步骤,u S,A B C D E F G,0,-,0,1,A,A,0,7 1 ,2,C,A,C,0,4 1 5 4 ,3,F,A,C,F,0,4 1 14 5 4 11,4,B,A,C,F,B,0,4 1 12 5 4 11,5,E,A,C,F,B,E,0,4 1 12 5 4 7,6,G,A,C,F,B,E,G,0,4 1 12 5 4 7,可以在,Dijkstra,算法的基础之上以如下方法找到最短路径:从终点往回走,找到它的前导顶点,使得它们之间的标号的差等于连接它们边的权重,如此下去直至到起点,从而找到一条最短路径。,12,步骤 u S,作业,用,Dijkstra,算法求出下图中从顶点,a,到其它所有顶点的最短路径及及长度。,13,作业 用Dijkstra算法求出下图中从顶点a到其它所有顶点,有向图中求最短路径的,Dijkstra,算法,设,S,j,是带权有向图,G,中自顶点,1,到顶点,j,的最短有向路的长度,步骤,1,:置,P,=1,,,T=2,3,n,且,S,1,=0,,,S,j,=w,1j,,,j,=,2,3,n,。,步骤,2,:在,T,中寻找一点,k,,使得,S,k,=min,S,j,,置,P,=,P,k,,,T,=,T,-,k,。若,T,=,,终止;否则,转向步骤,3,。,步骤,3,:对,T,中每一点,j,,置,S,j,=,min,S,j,,,S,k,+w,kj,,然后转向步骤,2,。,算法经过,n,-1,次循环结束。,14,有向图中求最短路径的Dijkstra算法设Sj是带权有向图G,任意两点间的最短路径,Floyd,算法,Warshall,算法,15,任意两点间的最短路径Floyd算法15,任意两点间的最短路径,-,Floyd,算法,首先定义两种矩阵运算:,定义,1,已知矩阵,A,=(,a,ij,),m,l,,,B,=(,b,ij,),l,n,,规定,C,=,A,B,=(,c,ij,),m,n,,,其中,c,ij,=min(,a,i1,+,b,1j,a,i2,+,b,2j,a,il,+,b,lj,),定义,2,已知矩阵,A,=(,a,ij,),m,n,,,B,=(,b,ij,),m,n,,规定,C,=,A,B,=(,d,ij,),m,n,,,其中,d,ij,=min(,a,ij,b,ij,),16,任意两点间的最短路径-Floyd算法首先定义两种矩阵运算:1,例 已知矩阵,W,,求,W,W,17,例 已知矩阵W,求WW17,例 已知矩阵,W,,求,W,W,c,ij,=min(,a,i1,+,b,1j,a,i2,+,b,2j,a,il,+,b,lj,),18,例 已知矩阵W,求WWcij=min(ai1+b1j,a,c,ij,=min(,a,i1,+,b,1j,a,i2,+,b,2j,a,il,+,b,lj,),19,cij=min(ai1+b1j,ai2+b2j,ai,任意两点间的最短路径,-,Floyd,算法,算法原理,:,若,W,=(,w,ij,),nn,是图,G,的权矩阵,计算,W,2,,,W,3,,,,,W,n,及,S,,,其中,W,k,=,W,k-1,W=,(,w,ij,k,),nn,;,S,=,W,W,2,W,3,W,n,=,(,s,ij,),nn,。,则,w,ij,k,表示顶点,i,到顶点,j,经过,k,条边且权和最小的路径,,s,ij,表示顶点,i,到顶点,j,权和最小的路径(最短路径)。,20,任意两点间的最短路径-Floyd算法算法原理:20,例 求下图中任意两点间最短路径的长度。,21,例 求下图中任意两点间最短路径的长度。21,22,22,由,s,16,知,顶点,v1,到,v6,的最短路径为,6,;,由,s,35,知,顶点,v3,到,v5,的最短路径为,2,;,由,s,45,知,顶点,v4,到,v5,没有最短路径;,23,由s16知,顶点v1到v6的最短路径为6;23,任意两点间的最短路径,-,Warshall,算法,算法原理:,(,1,)输入图,G,的权矩阵,W,;,(,2,)置,k,:=1,;,(,3,)置,i,:=1,;,(,4,)修改矩阵,W,中的权值,,w,ij,:=min(,w,ij,w,ik,+,w,kj,),,,j,=1,2,n,;,(,5,),i,:=,i,+1,,若,i,n,,转,(4),;,(,6,),k,:=,k,+1,,若,k,n,,转,(3),;否则停止。,24,任意两点间的最短路径-Warshall算法算法原理:24,例 求下图中任意两点间最短路径的长度。,w,ij,:=min(,w,ij,w,ik,+,w,kj,),25,例 求下图中任意两点间最短路径的长度。wij:=min(w,w,ij,:=min(,w,ij,w,ik,+,w,kj,),26,wij:=min(wij,wik+wkj)26,27,27,Floyd,算法的改进,Floyd,算法和,Warshall,算法只能给出任意两点间的最短路径的长度。,改进的,Warshall,算法不仅能够给出任意两点间的最短路径的长度,同时也给出具体的最短路径。,28,Floyd算法的改进 Floyd算法和Warsh,改进后的,Warshall,算法,算法原理:,(,1,)输入图,G,的权矩阵,W,=(,w,ij,),nn,和矩阵,P,=(,p,ij,),nn,,,其中,p,ij,=,i,。,(,2,)置,k,:=1,;,(,3,)置,i,:=1,;,(,4,)修改矩阵,W,和,P,中的值,,w,ij,:=min(,w,ij,w,ik,+,w,kj,),,,j,=1,2,n,;,p,ij,=,p,kj,,,j,=1,2,n,;,(,5,),i,:=,i,+1,,若,i,n,,转,(4),;,(,6,),k,:=,k,+1,,若,k,n,,转,(3),;否则停止。,矩阵,P,中,p,ij,的值是最短路径上从,i,到,j,被访问的最后一个顶点,所以利用该矩阵可以重构最短路径。,29,改进后的Warshall算法算法原理:矩阵P中pij的值是最,带负权图中的单源最短路径问题,Dijkstra,算法能够用于求带负权图中的指定两点间的最短路径?,30,带负权图中的单源最短路径问题Dijkstra算法能够用于求带,例 求下图中顶点,a,到,c,的最短路径。,如果用,Dijkstra,算法,则求出的最短路径为,ac,,而不是,abc,。,31,例 求下图中顶点a到c的最短路径。如果用Dijkstra算法,带负权图中的单源最短路径问题,Bellman-Ford,算法,该算法有一个限制条件,即要求图中不能包含权和为负值的回路。,32,带负权图中的单源最短路径问题Bellman-Ford算法32,Bellman-Ford,算法,Bellman-Ford,算法的目的是构造一个最短路径长度数组序列,dist,1,v,dist,2,v,dist,n,-1,v,,其中,dist,1,v,表示从起点,u,到图中其它所有顶点,v,的只经过一条边的长度,,dist,k,v,表示从起点,u,到顶点,v,的最多经过,k,条边的最短路径的长度。,Bellman-Ford,算法,最终的目的是算出,dist,n,-1,v,。,dist,1,v,的生成:,dist,1,u,=0,;若,是图中的有向边,则,dist,1,v,=,w,uv,,否则,dist,1,v,=,。,dist,k,v,的生成:,dist,k,v,=min,dist,k-1,v,min,dist,k-1,j,+,w,jv,。,33,Bellman-Ford算法 Bellman-Fo,
展开阅读全文