数据结构第七讲(4)最短路径

1、n7.6 关键路径关键路径u问题提出问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始每个事件表示在它之前的活动已完成，在它之后的活动可以开始例例 设一个工程有设一个工程有11项活动，项活动，9个事件个事件事件事件 V1表示整个工程开始表示整个工程开始事件事件V9表示整个工程结束表示整个工程结束问题：（问题：（1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？987645321a1=6a2=4

2、a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4u定义定义FAOE网网(Activity On Edge)也叫边表示活也叫边表示活动的网。动的网。AOE网是一个带权的有向无环图，其网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持中顶点表示事件，弧表示活动，权表示活动持续时间续时间F路径长度路径长度路径上各活动持续时间之和路径上各活动持续时间之和F关键路径关键路径路径长度最长的路径叫路径长度最长的路径叫FVe(j)表示事件表示事件Vj的最早发生时间的最早发生时间FVl(j)表示事件表示事件Vj的最迟发生时间的最迟发生时间Fe(i)表示活动表示活动a

3、i的最早开始时间的最早开始时间Fl(i)表示活动表示活动ai的最迟开始时间的最迟开始时间Fl(i)-e(i)表示完成活动表示完成活动ai的时间余量的时间余量F关键活动关键活动关键路径上的活动叫关键路径上的活动叫，即，即l(i)=e(i)的活动的活动u问题分析问题分析F如何找如何找e(i)=l(i)的关键活动？的关键活动？设活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：（则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkaiF如何求如何求Ve(j)和和Vl(j)？(1)从从Ve(1)=0开始向前递推开始向前递推为头的弧的集合是所有以其

4、中jTnjTjijidutiVeMaxjVei2 ,),()()(2)从从Vl(n)=Ve(n)开始向后递推开始向后递推为尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(u求关键路径步骤F求Ve(i)F求Vl(j)F求e(i)F求l(i)F计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266

5、046258377077071031616014140033n7.7 最短路径u问题提出用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市表示城市边边表示城市间的交通联系表示城市间的交通联系权权表示此线路的长度或沿此线路运输所花的时间或费用等表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径各边上权值之和最小的一条路径最短路径最短路径u从某个源点到其余各顶点的最短路径5164320856230137173291

6、3长度最短路径813192120F迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：按路径长度递增次序产生最短路径算法：把把V分成两组：分成两组：（1）S：已求出最短路径的顶点的集合：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合：尚未确定最短路径的顶点集合将将T中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到S中，中，保证：（保证：（1）从源点）从源点V0到到S中各顶点的最短路径长度都不大于中各顶点的最短路径长度都不大于 从从V0到到T中任何顶点的最短路径长度中任何顶点的最短路径长度 （2）每个顶点对应一个距离值）每个顶点对应一

7、个距离值 S中顶点：从中顶点：从V0到此顶点的最短路径长度到此顶点的最短路径长度 T中顶点：从中顶点：从V0到此顶点的只包括到此顶点的只包括S中顶点作中间中顶点作中间 顶点的最短路径长度顶点的最短路径长度依据：可以证明依据：可以证明V0到到T中顶点中顶点Vk的最短路径，或是从的最短路径，或是从V0到到Vk的的 直接路径的权值；或是从直接路径的权值；或是从V0经经S中顶点到中顶点到Vk的路径权值之和的路径权值之和（反证法可证）（反证法可证）ShortestPath ( const int n, const int v ) for ( int i = 0; i n; i+) disti = Edg

8、evi; /dist数组初始化数组初始化 Si = 0; if ( i != v & disti MAXINT ) pathi = v; else pathi = -1; /path数组初始化数组初始化 Sv = 1; distv = 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 ( !Sj & distj min ) u = j; mi

9、n = distj; Su = 1; /将顶点将顶点u加入集合加入集合S for ( int w = 0; w n; w+ ) /修改修改 if ( !Sw & Edgeuw MAXINT & distu + Edgeuw distw ) distw = distu + Edgeuw; pathw = u; 138 30 32V2:813-1330 32V1:13-13302220V3:13-192220V4:19终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329u每一

10、对顶点之间的最短路径F方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)F方法二：弗洛伊德(Floyd)算法 算法思想：逐个顶点试探法 求最短路径步骤初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束F对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。F不可思议的是，只要按排适当，就能得到结果。F/ dist(i,j) 为从节点i到节点j的最短距离FFor i1 to n do F For j1 to n do F dist(i,j) = weight(i,j)F For k1 to n do / k为“中间节点” F if (dist(i,k) + dist(k,j) dist(i,j) F then / 是否是更短的路径？F dist(i,j) = dist(i,k) + dist(k,j)例ACB