最短路径问题-课件

,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,