2-5th-Graph-ShortestPathTopologicalSort.ppt

7.3 7.3 最短路径最短路径(Shortest Path)(Shortest Path)qq问题的提出问题的提出问题的提出问题的提出q从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市表示城市边边表示城市间的交通联系表示城市间的交通联系权权表示此线路的长度或沿此线路运输所花的时间或费用等表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径各边上权值之和最小的一条路径最短路径最短路径51643208562301371732913长度最短路径813192120qq最短路径定义最短路径定义最短路径定义最短路径定义qq最短路径类型最短路径类型最短路径类型最短路径类型单源点最短路径：单源点最短路径：单源点最短路径：单源点最短路径：多源点最短路径：多源点最短路径：多源点最短路径：多源点最短路径：给定带权有向图给定带权有向图G G和源点和源点v v，求从，求从v v到到G G中其余各顶点的最短路径。中其余各顶点的最短路径。给定带权有向图给定带权有向图G G，求，求G G中每一对顶中每一对顶点之间的最短路径。点之间的最短路径。7.3.1 7.3.1 单源点最短路径问题单源点最短路径问题7.3.1.17.3.1.1 弧上权值非负弧上权值非负1 *7.3.1.1 7.3.1.1 弧上权值为非负情形弧上权值为非负情形3.3.迪杰斯特拉迪杰斯特拉(Dijkstra)(Dijkstra)算法算法定义：定义：按路径长度递增的次序产生最短路径。按路径长度递增的次序产生最短路径。思思想想：首首先先求求出出从从源源点点v v0 0到到其其余余各各顶顶点点中中长长度度最最短短的的一一条条，然然后后参参照照它它求求出出长长度度次次短短的的一一条条最最短短路路径径，依依次次类类推推，直直到到从从源源点点v v0 0到到其其余余各各顶顶点点的的最最短短路路径全部求出为止。径全部求出为止。具具体体做做法法：设设集集合合S S存存放放已已经经求求出出的的最最短短路路径径的的终终点点，初初始始状状态态时时，集集合合S S中中只只有有一一个个源源点点v v0 0（S=vS=v0 0）。以以后后每每求求得得一一条条最最短短路路径径(v(v0 0，v vk k)，就就将将v vk k加入到集合加入到集合S S中，直到全部顶点都加入到集合中，直到全部顶点都加入到集合S S中，算法就可以结束了。中，算法就可以结束了。v 引进辅助向量引进辅助向量dist,disti表示表示当前所找到的当前所找到的从始点从始点v0到每个终点到每个终点vi的最短路径长度。初态为的最短路径长度。初态为:若从若从v到到vi有弧有弧,则则disti为弧上的权值为弧上的权值;否则置否则置disti为为。v 引引 入辅助数组入辅助数组path,pathi 表示从源点表示从源点v0到顶点到顶点vi的最短路径上的顶的最短路径上的顶点点vi的直接前驱顶点。的直接前驱顶点。v 下一条长度次短的路径是那一条下一条长度次短的路径是那一条?假设该次短路径的终点是假设该次短路径的终点是vk,则这条路径则这条路径或者是或者是(v,vk),或者是或者是(v,vj,vk)distj=Mindisti|vi V-S 思考：思考：（1 1）算法思想的）算法思想的“核心本质核心本质”是什么？是什么？（2 2）迪杰斯特拉）迪杰斯特拉(Dijkstra)(Dijkstra)算法如何实现？采用什么结构比较好算法如何实现？采用什么结构比较好？（3 3）如何记录最短路径）如何记录最短路径 值，路径上顶点集值，路径上顶点集？（4 4）如何记录已求得路径的）如何记录已求得路径的“终点终点”集？集？（5 5）如何参照）如何参照“最短最短”求求“次短次短”？2 1383032V2:813-1330?32V1:13-13302220V3:13终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-192220V4:19-2120V6:20516432085623013717329*3 *迪杰斯特拉算法迪杰斯特拉算法templatevoidShortestPathDij(constAdjListDirNetwork&g,intv0,int*path,WeightType*dist)WeightTypeminVal,infinity=g.GetInfinity();intv,u;/初始化初始化dist和和path数组数组 for(v=0;vg.GetVexNum();v+)distv=g.GetWeight(v0,v);if(distv=infinity)pathv=-1;elsepathv=v0;g.SetTag(v,UNVISITED);g.SetTag(v0,VISITED);4 *迪杰斯特拉算法迪杰斯特拉算法 for(inti=1;ig.GetVexNum();i+)minVal=infinity;u=v0;for(v=0;vg.GetVexNum();v+)/找最短的路径找最短的路径if(g.GetTag(v)=UNVISITED&distvminVal)u=v;minVal=distv;g.SetTag(u,VISITED);/修改路径和路径长度修改路径和路径长度 for(v=g.FirstAdjVex(u);v!=-1;v=g.NextAdjVex(u,v)if(g.GetTag(v)=UNVISITED&minVal+g.GetWeight(u,v)distv)distv=minVal+g.GetWeight(u,v);pathv=u;5 *7.3.1.2 7.3.1.2 弧上权值为任意值弧上权值为任意值(1)问题的引出：问题的引出：假设带权有向图假设带权有向图G G上弧的权值可能为负值。上弧的权值可能为负值。问题的解决：问题的解决：贝尔曼（贝尔曼（BellnamBellnam）和福特（）和福特（FordFord）提出了从源点逐次经）提出了从源点逐次经过其它顶点，以缩短到达终点的最短路径长度的方法。该方法过其它顶点，以缩短到达终点的最短路径长度的方法。该方法有一个限制条件：要求图中有一个限制条件：要求图中不能有路径长度为负值的回路不能有路径长度为负值的回路。当图中没有路径长度为负值的回路时，有当图中没有路径长度为负值的回路时，有n n个顶点的图个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有中任意两个顶点之间如果存在最短路径，此路径最多有n-1n-1条弧。条弧。ACB-202616A A为源点为源点:distC=16distC=16DistB=26DistB=266 *7.3.1.2 7.3.1.2 弧上权值为任意值弧上权值为任意值(2)构构造造一一个个最最短短路路径径长长度度的的数数组组序序列列：distdist1 1、distdist2 2、distdistn-1n-1。distdist1 1uu表表示示从从源源点点v v0 0直直接接到到终终点点u u的的最最短短路路径径的的长长度度，即即distdist1 1uuArcsvArcsv0 0uu；distdist2 2uu表表示示从从源源点点v v0 0出出发发最最多多经经过过两两条条弧弧（一一个个中中间间顶顶点点）到到达终点达终点u u的最短路径的长度，的最短路径的长度，distdistk kuu是是从从源源点点v v0 0出出发发最最多多经经过过不不构构成成带带负负长长度度回回路路的的k k条条弧弧（k-1k-1个中间顶点）到达终点个中间顶点）到达终点u u的最短路径的长度。的最短路径的长度。算法的结果就是计算出算法的结果就是计算出distdistn-1n-1uu。思考：思考：（1 1）distdist维数？维数？（2 2）能否用二维数组表示）能否用二维数组表示distdist？（3 3）distdist值如何变化？值如何变化？可可以以用用递递推推方方式式计计算算distn-1。设设已已经经求求出出distk-1i，i0，1，n-1，此此即即从从源源点点v0出出发发最最多多经经过过不不构构成成带带负负长长度度回回路路的的k-1条条到达终点到达终点i的最短路径的长度。的最短路径的长度。从从图图的的邻邻接接矩矩阵阵中中可可以以找找到到从从任任一一顶顶点点i直直接接到到达达另另一一顶顶点点u的的距距离离Arcsiu，利用递推公式：，利用递推公式：dist1uArcsv0u；distku=min distk-1u，min distk-1i+Arcsiu（4 4）distdist维数？维数？（5 5）代码实现？循环重数？）代码实现？循环重数？（6 6）算法复杂度？邻接矩阵）算法复杂度？邻接矩阵/邻接表？邻接表？NextNextNextNext7 *贝尔曼贝尔曼福特算法福特算法8 *贝尔曼贝尔曼福特算法福特算法templateVoidShortestPathBellmanFord(constAdjListDirNetwork&g,intv0,int*path,WeightType*dist)WeightType*distTemp,minVal,infinityg.GetInfinity();intv,u,vexNum=g.GetVexNum();distTemp=newWeightTypevexNum;for(v=0;vvexNum;v+)/初始化初始化path和和distdistv=(v0!=v)?g.GetWeight(v0,v):0;if(distv=infinity)pathv=-1;elsepathv=v0;9 *贝尔曼贝尔曼福特算法福特算法for(intk=2;kvexNum;k+)for(v=0;vvexNum;v+)distTempv=distv;for(u=0;uvexNum;u+)if(u!=v0)for(v=0;vdistvg.GetWeight(v,u)distTempu=distv+g.GetWeight(v,u);pathu=v;for(v=0;vvexNum;v+)distv=distTempv;10 *7.3.2 7.3.2 所有顶点之间的最短路径所有顶点之间的最短路径1.1.问题问题所所有有顶顶点点对对之之间间的的最最短短路路径径是是指指：对对于于给给定定的的有有向向网网G=(V,E)G=(V,E)，要要对对G G中中任任意意一一对对顶顶点点有有序序对对V V、W(VW)W(VW)，找找出出V V到到W W的最短距离和的最短距离和W W到到V V的最短距离。的最短距离。2.2.解决方法解决方法q 方方法法一一：每每次次以以一一个个顶顶点点为为源源点点，重重复复执执行行Dijkstra算算法法n次次 T(n)=O(n)q 方法二：弗洛伊德方法二：弗洛伊德(Floyd)算法算法11 *3.3.弗洛伊德弗洛伊德(Floyd)Floyd)算法算法基本思想：基本思想：设设nn方阵序列方阵序列A(k)（k=0、1、n-1）。）。A(k)ii=0;/对角线的矩阵元素都等于对角线的矩阵元素都等于0 A(k)ij：/从顶点从顶点i到顶点到顶点j经过的中间顶点序号不超过经过的中间顶点序号不超过k的的 /最短有向路径长度最短有向路径长度 初始：初始：A(-1)ij=Arcs ij;Steps:逐逐步步尝尝试试在在原原路路径径中中依依次次加加入入其其它它顶顶点点作作为为中中间间顶顶点点。如如果果增增加加中中间间顶顶点点后后，得得到到的的路路径径长长度度比比原原来来的的路路径径长长度度减减少少了了，则则以以此此新新路路径径代代替替原原路路径径，并并修修改改相相应应的的矩矩阵阵元素，代入新的更短的路径长度。元素，代入新的更短的路径长度。思考：与思考：与贝尔曼贝尔曼贝尔曼贝尔曼福特算法福特算法福特算法福特算法的异同？的异同？求最短路径步骤求最短路径步骤:初始时设置一个初始时设置一个n阶方阵阶方阵a，令其对角线元素为，令其对角线元素为0，若存在弧若存在弧，则对应元素则对应元素aij为权值为权值,即即 a(0)ij=arcsij；否则；否则aij为为。逐步试着在原直接路径中增加中间顶点，若加入中间点逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。后路径变短，则修改之；否则，维持原值。具体做法为：具体做法为：第一步，让所有边上加入中间顶点第一步，让所有边上加入中间顶点1，取，取aij与与ai1+a1j中较小的值作中较小的值作aij的值，完成后得到的值，完成后得到A(1)，第二步，让所有边上加入中间顶点第二步，让所有边上加入中间顶点2，取，取aij与与ai2+a2j中较小的值，完成后得到中较小的值，完成后得到a(2)，如此进行，如此进行下去，当第下去，当第n步完成后，得到步完成后，得到a(n)，a(n)即为我们所求结果，即为我们所求结果，a(n)ij表示顶点表示顶点i到顶点到顶点j的最短距离。的最短距离。所有顶点试探完毕，算法结束。所有顶点试探完毕，算法结束。12 弗洛伊德弗洛伊德(Floyd)(Floyd)算法算法V2V1V0abc1d641132223V3abcda0411b602c301d2230*Example4Example4shortest pathshortest path76847537思考题思考题思考题思考题:1.1.1.1.矩阵中的变化规律矩阵中的变化规律矩阵中的变化规律矩阵中的变化规律?2.2.2.2.代码中的变化规律的写法代码中的变化规律的写法代码中的变化规律的写法代码中的变化规律的写法?3.3.3.3.什么存储结构最方便什么存储结构最方便什么存储结构最方便什么存储结构最方便?13 template voidShortestPathFloyd(constAdjListDirNetwork&g,int*path,WeightType*dist)for(intu=0;ug.GetVexNum();u+)for(intv=0;vg.GetVexNum();v+)distuv=(u!=v)?g.GetWeight(u,v):0;if(u!=v&distuvg.GetInfinity()pathuv=u;elsepathuv=1;for(intk=0;kg.GetVexNum();k+)for(inti=0;ig.GetVexNum();i+)for(intj=0;jg.GetVexNum();j+)if(distik+distkjdistij)distij=distik+distkj;pathij=pathkj;*弗洛伊德弗洛伊德(Floyd)算法算法14 *7.4 7.4 活动网络活动网络(Activity(Activity Network)Network)qq问题的提出问题的提出问题的提出问题的提出-学生选修课程问题学生选修课程问题7.4.1 7.4.1 用顶点表示活动的网络用顶点表示活动的网络顶点表示课程有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序qq定义定义定义定义有向无环图有向无环图(directed acycline graph)：一个无环一个无环的有向图的有向图,简称简称DAG图图.有向树、有向树、DAG图和有向图例图和有向图例顶点表示活动（顶点表示活动（activity on vertices AOVactivity on vertices AOV）的网络）的网络 AOVAOV是用以表示一个工程的有向图是用以表示一个工程的有向图 图中的顶点表示一项子工程，即活动图中的顶点表示一项子工程，即活动 弧表示两活动之间的先后次序弧表示两活动之间的先后次序 以计算机专业课程学习工程为例以计算机专业课程学习工程为例C0C1C2C3C4C5C0 数据结构数据结构C1 操作系统操作系统C2 组成原理组成原理C3 数据库系统数据库系统C4 面向对象程序设计面向对象程序设计C5 计算机网络计算机网络 拓扑排序拓扑排序(Topological Sort)(Topological Sort)把把AOV网络中各顶点网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程按照它们相互之间的优先关系排列成一个线性序列的过程叫叫.检测检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网网必定不存在环必定不存在环 拓扑排序的方法拓扑排序的方法v 在有向图中选一个没有前驱的顶点且输出之在有向图中选一个没有前驱的顶点且输出之v 从图中删除该顶点和所有以它为尾的弧从图中删除该顶点和所有以它为尾的弧v 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止驱的顶点为止NextNextNextNext思考题思考题思考题思考题:拓扑排拓扑排拓扑排拓扑排序结果是否唯序结果是否唯序结果是否唯序结果是否唯一一一一?为什么为什么为什么为什么?休息休息15 *拓扑排序例（拓扑排序例（2 2）拓扑序列：C1思考：思考：1.1.如何记录入度为如何记录入度为0 0的顶点？采用什么的顶点？采用什么结构结构/辅助手段比辅助手段比较好？较好？2.2.刚才演示的删去刚才演示的删去C1C1的所有出边的所有出边【理论理论上上】，实际的工程，实际的工程实现中是否真的删实现中是否真的删除边？如何处理？除边？如何处理？C1C2C3C4C5C6C7C8C9C10C11C12休息休息3.3.当有多个入度为当有多个入度为0 0的顶点时，能否同时将它的顶点时，能否同时将它们记录下来并形成一种线性关系？采用什么们记录下来并形成一种线性关系？采用什么结构结构/辅助手段比较好？辅助手段比较好？4.4.教材上的算法中技巧是什么？教材上的算法中技巧是什么？16 *拓扑排序例（拓扑排序例（2 2）C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1拓扑序列：C1 C2拓扑序列：C1 C2 C3拓扑序列：C1 C2 C3 C4拓扑序列：C1 C2 C3 C4 C5拓扑序列：C1 C2 C3 C4 C5 C7拓扑序列：C1 C2 C3 C4 C5 C7 C9拓扑序列：C1 C2 C3 C4 C5 C7 C9 C10拓扑序列：C1 C2 C3 C4 C5 C7 C9 C10 C12拓扑序列：C1 C2 C3 C4 C5 C7 C9 C10 C12 C11拓扑序列：C1 C2 C3 C4 C5 C7 C9 C10 C12 C11 C6拓扑序列：C1 C2 C3 C4 C5 C7 C9 C10 C12 C11 C6 C8思考：思考：1.1.实现拓扑排序的关键问题是什么？采用什么结构实现拓扑排序的关键问题是什么？采用什么结构/辅助手段比较好？辅助手段比较好？2.2.若将若将“学期学期”考虑进去，拓扑排序算法如何区分考虑进去，拓扑排序算法如何区分“学期学期”这个概念？这个概念？3.3.上例中一定排在上例中一定排在C6C6前面的结点有哪些？前面的结点有哪些？C1C2C3C4C5C6C7C8C9C10C11C12休息休息17 *拓扑排序算法拓扑排序算法(1)(1)存存储储结结构构：AOVAOV网网络络：邻邻接接表表；辅辅助助变变量量：顶顶点点入入度度数数组组InDegreeInDegree ，记录各个顶点的入度。，记录各个顶点的入度。(2)(2)算法步骤：算法步骤：（1 1）建立入度为零的顶点建立入度为零的顶点栈（队列？其他？）栈（队列？其他？）；（2 2）当入度为零的顶点栈为空时算法转步骤（当入度为零的顶点栈为空时算法转步骤（6 6），否则继），否则继续步骤（续步骤（3 3）；）；（3 3）入度为零的顶点栈中栈顶元素入度为零的顶点栈中栈顶元素v v出栈出栈,并输出顶点并输出顶点v v；（4 4）从从AOVAOV网网络络中中删删去去顶顶点点v v和和所所有有从从顶顶点点v v发发出出的的弧弧vj，并将顶点并将顶点j j的入度减一；的入度减一；（5 5）如如果果顶顶点点j j入入度度减减至至0 0，则则将将该该顶顶点点进进入入入入度度为为零零的的顶顶点点栈（队列？其他？）栈（队列？其他？）；转步骤（；转步骤（2 2）；）；（6 6）如果输出顶点个数少于如果输出顶点个数少于AOVAOV网络的顶点个数，则输出网网络的顶点个数，则输出网络中存在有向环的信息；算法结束。络中存在有向环的信息；算法结束。思考题思考题思考题思考题1:1:1:1:入度如何记录入度如何记录入度如何记录入度如何记录?思考题思考题思考题思考题2:2:2:2:为什么建立入度为为什么建立入度为为什么建立入度为为什么建立入度为0 0 0 0的栈的栈的栈的栈?思考题思考题思考题思考题3:3:3:3:采用什么存储结构比较好采用什么存储结构比较好采用什么存储结构比较好采用什么存储结构比较好?针对每个步骤分析针对每个步骤分析针对每个步骤分析针对每个步骤分析休息休息18 *拓扑排序算法拓扑排序算法(3)(3)(3)(3)作相应修改后图邻接表的类定义：作相应修改后图邻接表的类定义：作相应修改后图邻接表的类定义：作相应修改后图邻接表的类定义：class Graph friend class VertexNode;friend class ArcNode;private VertexNode *VertexesTable;int*InDegree;/入度数组，记录每一个顶点的入度 int CurrentNumVertexes;当前的顶点数 int CurrentNumArcs;/当前的边（或弧）数 int GetVertexPos(const char&v);/取顶点v在数组中的位置 public:Graph(char v ,int num=MaxVertexes);/构造函数 void TopologicalOrder();/拓扑排序;(4)(4)(4)(4)修改后的构造函数：修改后的构造函数：修改后的构造函数：修改后的构造函数Graph(vertexType v ,int num=MaxVertexes):CurrentNumVertexes(0),CurrentNumArcs(0)/Initialization int e,t,h;/弧数、输入弧的弧头、弧尾在顶点表中的位置 vertexType tail,head;/输入弧时的弧头、弧尾 arcType w;VertexesTable=new VertexNode MaxVertexes;InDegree=new int MaxVertexes;/创建入度表 for(int i=0;i e;/输入边的条数 for(i=0;i tail head w;/输入一条边 if(t=GetVertexPos(tail)=-1)cout”输入的顶点(tail)不存在”;else if(h=GetVertexPos(head)=-1)cout”输入的顶点(head)不存在”;else InsertArc(h,t,w);/插入一条边 InDegreet+;/顶点t的入度加一 思考题思考题思考题思考题:如何建立入度为如何建立入度为如何建立入度为如何建立入度为0 0 0 0的栈的栈的栈的栈?休息休息19 *拓扑排序算法拓扑排序算法实现技巧实现技巧 利用利用InDegree 建立入度为建立入度为0的顶点的的顶点的静态静态链链栈。栈。栈初始状态：栈初始状态：top=-1;顶点顶点i 进栈：进栈：InDegreei=top;top=i;出栈：出栈：j=top;top=InDegreetop;C0C1C2C3C4C5301031012345 初始出栈出栈j=4;top=2top=-1top-12toptop思考思考1 1：改入度为改入度为0 0顶点顶点的值为当前的值为当前toptop，对，对“入度入度”有无影响？有无影响？思考思考2 2：出栈时不改写出栈时不改写“入度入度”值有无影响？值有无影响？思考思考3 3：静态链栈和一静态链栈和一般的静态存储栈有什么般的静态存储栈有什么异同？异同？思考思考4 4：此处用静态链此处用静态链栈的优点是什么？栈的优点是什么？思考思考5 5：如果下标为如果下标为0 0的的顶点入度变为顶点入度变为0 0时对时对“扫描入度是扫描入度是0 0的所有顶的所有顶点点”有无影响？有无影响？Why?Why?思考思考6 6：用栈的目的是什：用栈的目的是什么（后进先出）？能否用么（后进先出）？能否用队列？如果用队列，能否队列？如果用队列，能否和入度数组共享空间？和入度数组共享空间？休息休息20 *研讨题研讨题讲解迪杰斯特拉讲解迪杰斯特拉(Dijkstra)(Dijkstra)算法实现的具体算法实现的具体思想和步骤，分析算法与存储结构间的关思想和步骤，分析算法与存储结构间的关系。以系。以P262P262第第4 4题为例题为例第二题：讲解贝尔曼第二题：讲解贝尔曼-福特（福特（Bellnam-Bellnam-FordFord）算法实现的具体思想和步骤，分析）算法实现的具体思想和步骤，分析算法与存储结构间的关系。以算法与存储结构间的关系。以P262P262第第5 5题题为例为例21