数据结构课件chp6.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图的基本概念,图的存储表示,图的遍历与连通性,最小生成树,最短路径,活动网络,第六章 图,图的基本概念,图定义,图是由顶点集合,(vertex),及顶点间的关系集合组成的一种数据结构,：,Graph,(,V,E,),其中,V,=,x,|,x,某个数据对象,是顶点的有穷非空集合；,E,=(,x,y,)|,x,y,V,或,E,=,|,x,y,V,&,Path,(,x,y,),是顶点之间关系的有穷集合，也叫做边,(edge),集合。,Path,(,x,y,),表示从,x,到,y,的一条单向通路,它是有方向的。,有向图与无向图,在有向图中，顶点对,是有序的。在无向图中，顶点对,(x,y),是无序的。,完全图,若有,n,个顶点的无向图有,n,(,n,-1)/2,条边,则此图为完全无向图。有,n,个顶点的有向图有,n,(,n-,1),条边,则此图为完全有向图。,邻接顶点,如果,(,u,v,),是,E,(G),中的一条边，则称,u,与,v,互为邻接顶点,。,权,某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。,子图,设有两个图,G,(,V,E,),和,G,(,V,E,),。若,V,V,且,E,E,则称 图,G,是 图,G,的子图。,顶点的度,一个顶点,v,的度是与它相关联的边的条数。记作,TD(,v,),。,在有向图中,顶点的度等于该顶点的入度与出度之和。,顶点,v,的入度,是以,v,为终点的有向边的条数,记作,ID(,v,),;,顶点,v,的出度,是以,v,为始点的有向边的条数,记作,OD(,v,),。,路径,在图,G,(,V,E,),中,若从顶点,v,i,出发,沿一些边经过一些顶点,v,p,1,v,p,2,v,pm,，到达顶点,v,j,。则称顶点序列,(,v,i,v,p,1,v,p,2,.,v,pm,v,j,),为从顶点,v,i,到顶点,v,j,的路径,。它经过的边,(,v,i,v,p,1,),、,(,v,p,1,v,p,2,),、,.,、,(,v,pm,v,j,),应是属于,E,的边。,路径长度,非带权图的路径长度是指此路径上边的条数。,带权图的路径长度是指路径上各边的权之和。,简单路径,若路径上各顶点,v,1,v,2,.,v,m,均不互相重复,则称这样的路径为简单路径。,回路,若路径上第一个顶点,v,1,与最后一个顶点,v,m,重合,则称这样的路径为回路或环。,连通图与连通分量,在无向图中,若从顶点,v,1,到顶点,v,2,有路径,则称顶点,v,1,与,v,2,是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,强连通图与强连通分量,在有向图中,若对于每一对顶点,v,i,和,v,j,都存在一条从,v,i,到,v,j,和从v,j,到,v,i,的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,生成树,一个连通图的生成树是它的极小连通子图，在,n,个顶点的情形下，有,n,-1,条边。但有向图则可能得到它的由若干有向树组成的生成森林。,本章不予,讨论的图,图的抽象数据类型,class Graph,public:,Graph,(),;,void,InsertVertex,(,const Type&,vertex,),;,void,InsertEdge,(,const int,v,1,const int,v,2,int,weight,),;,void,RemoveVertex,(,const int,v,),;,void,RemoveEdge,(,const int,v,1,const int,v,2),;,int,IsEmpty,(),;,int,NumberOfEdges();,int,NumberOfVertices();,图的存储表示,在图的邻接矩阵表示中，有一个,记录各个顶点信息,的,顶点表,，还有一个,表示各个顶点之间关系,的,邻接矩阵,。,设图,A=(,V,E,),是一个有,n,个顶点的图，则图的邻接矩阵是一个二维数组,A,.edge,n,n,，定义：,无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,邻接矩阵,(Adjacency Matrix),在有向图中,统计第,i,行,1,的个数可得顶点,i,的出度，统计第,j,列,1,的个数可得顶点,j,的入度。,在无向图中,统计第,i,行(列)1 的个数可得顶点,i,的度。,网络的邻接矩阵,邻接表,(Adjacency List),无向图的邻接表,把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标,dest,和指向同一链表中下一个边结点的指针,link,。,有向图的邻接表和逆邻接表,在有向图的邻接表中，第,i,个边链表链接的边都是,顶点,i,发出的边,。也叫做,出边表,。,在有向图的逆邻接表中，第,i,个边链表链接的边都是,进入顶点,i,的边,。也叫做,入边表,。,带权图的边结点中保存该边上的权值,cost,。,在邻接表的边链表中，,各个边结点的链入顺序任意，视边结点输入次序而定。,设图中有,n,个顶点，,e,条边，则,用邻接表表示无向图时,，需要,n,个顶点结点，,2,e,个边结点；用,邻接表表示有向图时,，若不考虑逆邻接表，只需,n,个顶点结点，,e,个边结点。,邻接多重表,(Adjacency Multilist),在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。,无向图的情形,边结点的结构,mark vertex,1,vertex,2,path,1,path,2,其中，,mark,是记录是否处理过的标记；,vertex,1,和,vertex,2,是依附于该边的两顶点位置。,path,1,域是链接指针，指向下一条依附于,顶点,vertex,1,的边；,path,2,也是链接指针，指向下一条依附于,顶点,vertex,2,的边。需要时还可设置一个存放与该边相关的权值的域,cost,。,顶点结点的结构,存储顶点信息的结点表,以顺序表方式组织,，每一个顶点结点有两个数据成员：其中，,data,存放与该顶点相关的信息，,Firstout,是指示第一条依附于该顶点的边的指针。,在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。,从,顶点,i,出发,可以循链找到所有依附于该顶点的边也可以找到它的所有邻接顶点。,邻接多重表的结构,data Firstout,邻接多重表的结构,图的遍历与连通性,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历,(Graph Traversal),。,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组,visited,，它的初始状态为,0,，在图的遍历过程中，一旦某一个顶点,i,被访问，就立即让,visited,i,为,1,，防止它被多次访问。,深度优先搜索,DFSDepth First Search),深度优先搜索的示例,DFS,在访问图中某一起始顶点,v,后，由,v,出发，访问它的任一邻接顶点,w,1,；再从,w,1,出发，访问与,w,1,邻 接但还没有访问过的顶点,w,2,；然后再从,w,2,出发，进行类似的访问，,如此进行下去，直至到达所有的邻接顶点都被访问过的顶点,u,为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,图的深度优先搜索算法,viod,Graph,DFS,(,const int,v,int,visited,),cout,GetValue,(,v,),;,/,访问顶点,v,visited,v,=1,;,/,顶点,v,作访问标记,int,w,=,GetFirstNeighbor,(,v,),;,/,取,v,的第一个邻接顶点,w,while,(,w,!=,-,1),/,若邻接顶点,w,存在,if,(!,visited,w,),DFS,(,w,visited,),;,/,若,顶点,w,未访问过,递归访问顶点,w,w,=,GetNextNeighbor,(,v,w,),;,/,取顶点,v,的排在,w,后面的下一个邻接顶点,void,GraphDFS,(),visited,=,new,Boolean,n,;,/,创建数组,visited,for,(,int,i=,0,;,i n,;,i,+),visited,i,=0,;,/,访问标记数组,visited,初始化,DFS,(0),;,delete,visited,;,/,释放,visited,算法分析,图中有,n,个顶点，,e,条边。,如果用邻接表表示图，沿,Firstout,link,链可以找到某个顶点,v,的所有邻接顶点,w,。由于总共有,2,e,个边结点，所以扫描边的时间为,O(,e,),。而且对所有顶点递归访问,1,次，所以遍历图的时间复杂性为,O(,n,+,e,),。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为,O(,n,),，则遍历图中所有的顶点所需的时间为,O(,n,2,),。,广度优先搜索,BFS,(Breadth First Search,),广度优先搜索的示例,广度优先搜索过程 广度优先生成树,使用广度优先搜索在访问了起始顶点,v,之后，由,v,出发，依次访问,v,的各个未曾被访问过的邻接顶点,w,1,w,2,w,t,，然后再顺序访问,w,1,w,2,w,t,的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，,如此做下去，直到图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。,与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组,visited,，给被访问过的顶点加标记。,图的广度优先搜索算法,void,Graph,:,BFS,(,const int,v,),visited,=,new int,NumCertices,;,/,创建,visited,for,(,int,i=,0,;,i NumVertices,;,i,+),visited,i,=0,;,/,visited,初始化,cout,GetValue,(,v,),;,visited,v,=1,;,Queue,q,;,q.EnQueue,(,v,),;,/,访问,v,进队列,while,(!,q.IsEmpty,(),/,队空搜索结束,v,=,q.DeQueue,(),;,/,不空,出队列,int,w,=,GetFirstNeighbor,(,v,),;,/,取顶点,v,的,第一个邻接顶点,w,while,(,w,!=,-,1),/,若邻接顶点,w,存在,if,(!,visited,w,),/,若该邻接顶点未访问过,cout,GetValue,(,w,),;,/,访问,visited,w,=1,;,q.EnQueue,(,w,),;,/,进队,w,=,GetNextNeighbor,(,v,w,),;,/,取顶点,v,的排在,w,后面的下一邻接顶点,/,重复检测,v,的所有邻接顶点,delete,visited,;,算法分析,如果使用邻接表表示图，则循环的总时间代价为,d,0,+d,1,+d,n,-1,=O(,e,),，其中的,d,i,是顶点,i,的度。,如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的,n,个元素，总的时间代价为,O(,n,2,),。,连通分量,(Connected component),当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图,(,连通分量,),的所有顶点。,若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。,在算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,确定连通分量的算法,void,Graph,:,Components,(),visited,=,new int,NumCertices,;,/,创建,visited,for,(,int,i=,0,;,i NumVertices,;,i,+),visited,i,=0,;,/,visited,初始化,for,(,i=,0,;,i NumVertices,;,i,+),if,(!,visited,i,),/,检测所有顶点是否访问过,DFS,(,i,visited,),;,/,从未访问的顶点出发访问,OutputNewComponent,(),;,/,输出一个连通分量,delete,visited,;,/,释放,visited,重连通分量,(Biconnected Component),在无向连通图,G,中，当且仅当删去,G,中的顶点,v,及,所有依附于,v,的所有边,后，可将图分割成两个或两个以上的连通分量，则称顶点,v,为,关节点,。,没有,关节点,的连通图叫做重连通图。,在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。,一个连通图,G,如果不是重连通图，那么它可以包括几个重连通分量。,在一个无向连通图,G,中,重连通分量可以利用深度优先生成树找到。,dfn,顶点的深度优先数，标明进行深度优先搜索时各顶点访问的次序。,如果在深度优先生成树中，,顶点,u,是,顶点,v,的祖先,则有,dfn,u,dfn,v,。,深度优先生成树的根是,关节点,的充要条件是,它至少有两个子女,。,其它顶点,u,是,关节点,的充要条件是,它至少有一个子女,w,从,w,出发,不能通过,w,、,w,的子孙及一条回边所组成的路径到达,u,的祖先,。,在图,G,的每一个顶点上定义一个,low,值，,low,u,是从,u,或,u,的子孙,出发通过,回边,可以到达的,最低深度优先数,。,u,是关节点的充要条件是：,u,是具有两个以上子女的生成树的根,u,不是根，但它有一个子女,w,，使得,low,w,dfn,u,这时,w,及其子孙不存在指向顶点,u,的祖先的回边。,low,u,=min,dfn,u,min,low,w,|,w,是,u,的一个子女,min,dfn,x,|(,u,x,),是一条回边,计算dfn,与,low,的算法,(1),void,Graph,:,DfnLow,(,const int,x,),/,公有函数：从顶点,x,开始深度优先搜索,int,num,=1,;,/,num,是访问计数器,dfn,=,new int,NumVertices,;,low,=,new int,NumVertices,;,/,dfn,是深度优先数,low,是最小祖先访问顺序号,for,(,int,i=,0,;,i 1,时输出重连通分量（,1,）,void,Graph,:,Biconnected,(),/,公有函数：从顶点,0,开始深度优先搜索,int,num,=1,;,/,访问计数器,num,dfnnew int,NumVertices,;,/,dfn,是深度优先数,low,=,new int,NumVertices,;,/,low,是最小祖先号,for,(,int,i=,0,;,i 1,时输出重连通分量（,2,）,void,Graph,:,Biconnected,(,const int,u,const int,v,),/,私有函数：计算,dfn,与,low,根据其重连通分量输,/,出,Graph,的边。在产生的生成树中,v,是,u,的双亲,/,结点,S,是一个初始为空的栈，应声明为图的数,/,据成员。,int,x,y,w,;,dfn,u,=,low,u,=,num,+,;,w,=GetFirstNeighbor,(,u,),;,/,找顶点,u,的第一个邻接顶点,w,while,(,w,!=,-,1),if,(,v,!=,w,&,dfn,w,=,dfn,u,),/,无回边,原来的重连通分量结束,cout,“,新重连通分量,:”,end1;,do,(,x,y,)=,S.Pop,(),;,cout,x,y,endl;,while,(,x,y,),与,(,u,w,),不是同一条边,),;,/,输出该重连通分量的各边,else if,(,w,!=,v,),/,有回边,计算,low,u,=,min,2(,low,u,dfn,w,),;,/,根据回边另一顶点,w,调整,low,uw,=,GetNextNeighbor,(,u,w,),;,/,找顶点,u,的邻接顶点,w,的下一个邻接顶点,算法,Biconnected,的时间代价是,O(,n,+,e,),。其中,n,是该连通图的顶点数，,e,是该连通图的边数。,此算法的前提条件是连通图中至少有两个顶点,因为正好有一个顶点的图连一条边也没有。,最小生成树,(minimum cost spanning tree),使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。,按照生成树的定义，,n,个顶点的连通网络的生成树有,n,个顶点、,n,-,1,条边。,构造最小生成树的准则,必须只使用该网络中的边来构造最小生成树；,必须使用且仅使用,n,-,1,条边来联结网络中的,n,个顶点；,不能使用产生回路的边。,克鲁斯卡尔,(Kruskal),算法,克鲁斯卡尔算法的基本思想：,设有一个有,n,个顶点的连通网络,N,=,V,E,最初先构造一个只有,n,个顶点，没有边的非连通图,T,=,V,图中每个顶点自成一个连通分量。当在,E,中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到,T,中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。,算法的框架我们利用最小堆,(MinHeap),和并查集,(DisjointSets),来实现克鲁斯卡尔算法。,首先，利用最小堆来存放,E,中的所有的边,堆中每个结点的格式为,在构造最小生成树的过程中，最小堆中存放剩余的边，并且利用并查集的运算检查依附于一条边的两个顶点,tail,、,haed,是否在同一个连通分量,(,即并查集的同一个子集合,),上,是则舍去这条边；否则将此边加入,T,，同时将这两个顶点放在同一个连通分量上。随着各边逐步加入到最小生成树的边集合中，各连通分量也在逐步合并，直到形成一个连通分量为止。,tail head cost,边的两个顶点位置 边的权值,应用克鲁斯卡尔算法构造最小生成树的过程,最小生成树类定义,const int,MAXINT,=,机器可表示的,问题中不可能出现的大数,class,MinSpanTree,;,class,MSTEdgeNode,/,生成树边结点类定义,friend class,MinSpanTree,;,private:,int,tail,head,;,/,生成树各边的两顶点,int,cost,;,/,生成树各边的代价,;,class,MinSpanTree,/,生成树的类定义,public:,MinSpanTree,(,int,sz,=,MaxEdges,-,1),:,MaxSize,(,sz,),n,(0),edgevalue,=,new,MSTEdgeNode,MaxSize,;,int,Insert,(MSTEdgeNode,&,item,),;,/,将,item,加到最小生成树中,protected:,MSTEdgeNode,*,edgevalue,;,/,边值数组,int,MaxSize,n,;,/,最大边数,当前边数,;,利用克鲁斯卡尔算法建立最小生成树,void,Graph,:,Kruskal,(,MinSpanTree,&,T,),MSTEdgeNode e,;,/,边结点辅助单元,MinHeap,H,(,CurrentEdges,),;,int,NumVertices=VerticesList.last,;,/,顶点个数,UFSets,F,(,NumVertices,),;,/并查集,F,并初始化,for,(,int,u,=0,;,u,NumVertices,;,u,+),/,邻接矩阵,for,(,int,v,=,i,+1,;,v,NumVertices,;,v,+),if,(,Edge,u,v,!=,MAXINT,),/,检出所有边,e.tail,=,u,;,e.head,=,v,;,e.cost,=,w,;,H.Insert,(,e,),;,/,插入最小堆,int,count,=1,;,/,最小生成树加入边数的计数,while,(,count,NumVertices,),/,e,=,H.RemoveMin,(),;,/,从堆中退出一条边,u,=,F.Find,e.tail,),;,/,检测两端点的根,v,=,F.Find,(,e.head,),;,if,(,u,!=,v,),/,根不同,不在同一连通分量上,F.Union,(,u,v,),;,/,合并,T.Insert,(,e,),;,/,该边存入最小生成树,T,中,count,+;,在建立最小堆时需要检测邻接矩阵，计算的时间代价为,O(,n,2,),。且做了,e,次堆插入操作,每次插入调用了一个堆调整算法,SiftUp,(),算法,因此堆插入需要的时间代价为,O(,e,log,2,e,),。,在构造最小生成树时，最多调用了,e,次出堆操作,RemoveMin,(,),，,2,e,次并查集的,Find,(),操作，,n,-1,次,Union,(),操作，计算时间分别为,O(,e,log,2,e,),，,O(,e,log,2,n,),和,O(,n,),。,总的计算时间为,O(,e,log,2,e,+,e,log,2,n,+,n,),普里姆,(Prim),算法,普里姆算法的基本思想：,从连通网络,N,=,V,E,中的某一顶点,u,0,出发，选择与它关联的具有最小权值的边,(,u,0,v,),，将其顶点加入到,生成树的顶点集合,U,中。,以后每一步从,一个顶点在,U,中,，而,另一个顶点不在,U,中,的各条边中选择,权值最小的边,(,u,v,),把它的顶点加入到,集合,U,中。如此继续下去直到网络中的所有顶点都加入到生成树顶点集合,U,中为止。,采用邻接矩阵作为图的存储表示。,用普里姆算法构造最小生成树的过程,在构造过程中，还设置了两个辅助数组：,lowcost,存放,生成树顶点集合内顶点,到,生成树外各顶点,的各边上的当前最小权值；,nearvex,记录,生成树顶点集合外各顶点,距离,集合内哪个顶点,最近,(,即权值最小,),。,例子,若选择从顶点,0,出发，即,u,0,=0,，则两个辅助数组的初始状态为：,然后反复做以下工作：,在,lowcost,中选择,nearvex,i,-,1,&,lowcost,i,最小,的边,i,用,v,标记它。则选中的权值最小的边为,(,nearvex,v,v,),，相应的权值为,lowcost,v,。,将,nearvex,v,改为,-,1,表示它已加入生成树顶点集合。将边,(,nearvex,v,v,lowcost,v,),加入生成树的边集合。,取,lowcost,i,=min,lowcost,i,Edge,v,i,，即用,生成树顶点集合外各顶点,i,到,刚加入该集合的新顶点,v,的距离,Edge,v,i,与原来它们到生成树顶点集合中顶点的最短距离,lowcost,i,做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。,如果,生成树顶点集合外顶点,i,到,刚加入该集合的新顶点,v,的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改,nearvex,i,：,nearvex,i,=,v,。表示生成树外顶点,i,到生成树内顶点,v,当前距离最近。,继续重复得：,顶点,5,加入生成树顶点集合：,v,=5,v,=4,最后生成树中边集合里存入得各条边为：,(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14),利用普里姆算法建立最小生成树,void,Graph,:,Prim,(,MinSpanTree,&,T,),int,NumVertices,=,VerticesList.last,;,/,图中顶点数,lowcost,=,new int,NumVertices,;,nearvex,=,new int,NumVertices,;,for,(,int,i=,1,;,i NumVertices,;,i,+),lowcost,i,=,Edge,0,i,;,/,顶点,0,到各边的代价,nearvex,i,=0,;,/,及最短带权路径,nearvex,0=,-,1,;,/,顶点,0,加到生成树顶点集合,int,count,=0,;,/,生成树边值数组存放指针,MSTEdgeNode e,;,/,最小生成树结点辅助单元,for,(,i=,1,;,i NumVertices,;,i,+),/,循环,n,-1,次,加入,n,-1,条边,int,min,=MAXINT;,int,v,=0,;,for,(,int,j=,0,;,j NumVertices,;,j,+),if,(,nearvex,j,!=,-,1,&,lowcost,j,min,),v,=,j,;,min,=,lowcost,j,;,/,求生成树外顶点到生成树内顶点具有最小,/,权值的边,v,是,当前具最小权值的边的位置,if,(,v,),/,v=,0,表示再也找不到要求的顶点了,count,+,;,/,向生成树边值数组内存放,e,.,tail,=,nearvex,v,;,e,.,head,=,v,;,e,.,cost,=,lowcost,v,;,T.Insert,(,e,),;/,选出的边加入生成树,nearvex,v,=,-,1,;,/,作该边已加入生成树标记,for,(,j,=1,;,j,NumVertices,;,j,+),if,(,nearvex,j,!=,-,1,&,/,j,不在生成树中,Edge,v,j,lowcost,j,),/,需要修改,lowcost,j,=,Edge,v,j,;,nearvex,j,=,v,;,分析以上算法，设连通网络有,n,个顶点,，则该算法的时间复杂度为,O(,n,2,),它适用于边稠密的网络。,最短路径,(Shortest Path),最短路径问题：,如果从图中某一顶点,(,称为源点,),到达另一顶点,(,称为终点,),的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。,问题解法,边上权值非负情形的单源最短路径问题,Dijkstra,算法,边上权值为任意值的单源最短路径问题,Bellman,和,Ford,算法,所有顶点之间的最短路径,Floyd,算法,边上权值非负情形的单源最短路径问题,问题的提法：,给定一个带权有向图,D,与源点,v,，求从,v,到,D,中其它顶点的最短路径。,限定各边上的权值大于或等于,0,。,为求得这些最短路径，,Dijkstra,提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点,v,到其它各顶点的最短路径全部求出为止。,举例说明,Dijkstra,逐步求解的过程,引入一个辅助数组,dist,。它的每一个分量,dist,i,表示当前找到的从,源点,v,0,到,终点,v,i,的最短路径的长度。初始状态：,若从源点,v,0,到顶点,v,i,有边，则,dist,i,为该边上的权值；,若从源点,v,0,到顶点,v,i,没有边，则,dist,i,为,+,。,一般情况下，假设,S,是已求得的最短路径的终点的集合，则可证明：,下一条最短路径必然是从,v,0,出发，中间只经过,S,中的顶点便可到达的那些顶点,v,x,(,v,x,V-S,),的路径中的一条。,每次求得一条最短路径之后，其终点,v,k,加入集合,S,，然后,对所有的,v,i,V-S,，修改其,dist,i,值。,Dijkstra,算法可描述如下：,初始化：,S,v,0,;,dist,j,Edge,0,j,j,=1,2,n,-,1;,/,n,为图中顶点个数,求出最短路径的长度：,dist,k,min,dist,i,i,V,-,S,;,S,S,U,k,;,修改：,dist,i,min,dist,i,dist,k,+,Edge,k,i,对于每一个,i,V,-,S,;,判断：若,S=V,则算法结束，否则转,。,用于计算最短路径的图邻接矩阵类的定义,const int,NumVertices,=6,;,/,图中最大顶点个数,class,Graph,/,图的类定义,private:,int,Edge,NumVertices,NumVertices,;,/,邻接矩阵,int,dist,NumVertices,;,/,最短路径长度数组,int,path,NumVertices,;,/,最短路径数组,int,S,NumVertices,;,/,最短路径顶点集,public:,void,ShortestPath,(,const int,const int,),;,int,choose,(,const int,),;,;,计算从单个顶点到其它各个顶点的最短路径,void,Graph,:,ShortestPath,(const int,n,const int,v,),/,Graph,是一个具有,n,个顶点的带权有向图,各边上,/,的权值由,Edge,i,j,给出。本算法建立起一个数,/,组,:,dist,j,0,j,n,是当前求到的从顶点,v,到顶点,/,j,的最短路径长度,同时用数组,path,j,0,j,n,存,/,放求到的最短路径。,for,(,int,i=,0,;,i n,;,i,+),dist,i,=,Edge,v,i,;,/,dist,数组初始化,S,i,=0,;,if,(,i,!=,v,&,dist,i,MAXINT,),path,i,=,v,;,else,path,i,=,-,1,;,/path,数组初始化,S,v,=1,;,dist,v,=0,;,/,顶点,v,加入顶点集合,/,选择当前不在集合,S,中具有最短路径的顶点,u,for,(,i=,0,;,i n,-,1,;,i,+),int,min,=,MAXINT;,int,u,=,v,;,for,(,int,j=,0,;,j n,;,j,+),if,(!,S,j,&,dist,j,min,),u,=,j,;,min,=,dist,j,;,S,u,=1,;,/,将顶点,u,加入集合,S,for,(,int,w,=0,;,w,n,;,w,+),/,修改,if,(!,S,w,&,Edge,u,w,MAXINT&,dist,u,Edge,u,w,dist,w,),dist,w,=,dist,u,+,Edge,u,w,;,path,w,=,u,;,算法得时间复杂度,：,O(,n,2,),Dijkstra,算法中各辅助数组的变化,如何从表中读取源点,0,到终点,v,的最短路径？举顶点,4,为例,path4=2 path2=3,path3=0,，反过来排列，得到路径,0,3,2,4,，这就是源点,0,到终点,4,的最短路径。,边上权值为任意值的单源最短路径问题,带权有向图,D,的某几条边或所有边的长度可能为负值。利用,Dijkstra,算法，不一定能得到正确的结果。,源点,0,到终点,2,的最短路径应是,0,1,2,，其长度为,2,，它小于算法中计算出来的,dist,2,的值。,若设源点,v,=0,，使用,Dijkstra,算法，所得到的结果是不对的。,Bellman,和,Ford,提出了从源点逐次绕过其它顶点，以缩短到达终点的最短路径长度的方法。该方法有一个限制条件，即要求图中不能包含有由带负权值的边组成的回路。,当图中没有由带负权值的边组成的回路时，有,n,个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有,n-,1,条边。,我们将以此为依据考虑计算从,源点,v,到,其它顶点,u,的最短路径的长度,dist,u,。,Bellman-Ford,方法构造一个最短路径长度数组序列,dist,1,u,，dist,2,u,，,，,dist,n,-1,u,。其中，,dist,1,u,是从源点,v,到终点,u,的,只经过一条边,的最短路径的长度，,dist,1,u,=,Edge,v,u,；,dist,2,u,是从源点,v,最多经过两条边,到达终点,u,的最短路径的长度，,dist,3,u,是从源点,v,出发,最多经过不构成带负长度边回路的三条边,到达终点,u,的最短路径的长度，,，,dist,n,-1,u,是从源点,v,出发最多经过不构成带负长度边回路的,n,-1,条边,到达终点,u,的最短路径的长度。,算法的最终目的是计算出,dist,n,-1,u,。,可以用递推方式计算,dist,k,u,。dist,1,u,=,Edge,v,u,；,dist,k,u,=min,dist,k,-,1,u,min,dist,k,-,1,j,+,Edge,j,u,设已经求出,dist,k-,1,j,j,=0,1,n,-1,此即从源点,v,最多经过不构成带负长度边回路的,k,-,1,条边到达终点,j,的最短路径的长度。,从图的邻接矩阵中可以找到各个顶点,j,到达顶点,u,的距离,Edge,j,u,，计算,min,dist,k-,1,j,+,Edge,j,u,，可得从源点,v,绕过各个顶点，最多经过不构成带负长度边回路的,k,条边到达终点,u,的最短路径的长度。,用它与,dist,k-,1,u,比较，取小者作为,dist,k,u,的值。,图的最短路径长度,计算最短路径的,Bellman,和,Ford,算法,void,Graph,:,BellmanFord,(,const int,n,const int,v,),/,在带权有向图中有的边具有负的权值。从顶点,v,/,找到所有其它顶点的最短路径。,for,(,int,i=,0,;,i n,;,i,+),dist,i,=,Edge,v,i,;,if,(,i,!=,v,&,dist,i,MAXINT,),path,i,=,v,;,else,path,i,=-1,;,for,(,int,k,=2,;,k,n,;,k,+),for,(,int,u,=0,u,n,;,u,+),if,(,u,!=,v,),for,(,i=,0,;,i 0,&,Edge,i,u,dist,i,+,Edge,i,u,),dist,u,=,dist,i,+,Edge,i,u,;,path,u,=,i,;,所有顶点之间的最短路径,问题的提法：,已知一个各边权值均大于,0,的带权有向图，对每一对顶点,v,i,v,j,，要求求出,v,i,与,v,j,之间的最短路径和最短路径长度。,Floyd,算法的基本思想：,定义一个,n,阶方阵序列：,A,(-1),A,(0),A,(,n-,1),.,其中,A,(,-,1),i,j,=,Edge,i,j,；,A,(,k,),i,j,=