《数据结构》最短路径关键路径及其应用解析ppt课件.ppt

《《数据结构》最短路径关键路径及其应用解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构》最短路径关键路径及其应用解析ppt课件.ppt（82页珍藏版）》请在三一办公上搜索。

1、2022年11月16日星期三,第1页,最短路径、关键路径及其应用,所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。,最短路径问题,求从某个源点到其余各点的最短路径,2022年11月16日星期三,第3页,每一对顶点之间的最短路径,2022年11月16日星期三,第4页,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从源点到顶点v的最短路径是所有路径中长度最短者。,v2,给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。,V

2、5,V0,V2,V4,V1,V3,100,30,10,60,10,20,50,5,V0,V2,V4,V3,V5,V0,始点 终点 Di 最短路径,V1V2V3V4 V5,1030100,1030100,106030100,106030100,105030100,(V0, V2)(V0, V4)(V0, V5),(V0, V2)(V0, V4)(V0, V5),(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5),(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5),(V0, V2)(V0, V4, V3)(V0, V4)(V0, V5),10503090

3、,(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V5),10503090,(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V5),10503060,(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V3, V5),10503060,(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V3, V5),2022年11月16日星期三,第6页,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的最短路径的特点：,路径长度最短的最短路径的特点：,它只可能有两种情况：或者是直接从源点到

4、该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。,2022年11月16日星期三,第7页,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。,如何在计算机中求得最短路径？,2022年11月16日星期三,第9页,求最短路径的迪杰斯特拉算法：,一般情况下，Distk = 或者 = + 。,设置辅助数组Dist，其

5、中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。,Dijkstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：假设我们以邻接矩阵cost表示所研究的有向网。迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0 ，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素Si 为 0 ，否则为 1 。,另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为Di=costV0i

6、，i=1n。数组D中的数据随着算法的逐步进行要不断地修改定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使Dw的值最小。于是从源点到达w只通过S中的顶点，把 w 加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离： 取Dv和Dw+costwv中值较小的作为新的Dv重复上述，直到S中包含V中其余各顶点的最短路径。,V0 V1 V2 V3 V4 V5 V0 10 30 100V1 5 V2 50 V3 10 V4 20 60 V5 ,V0,V2,V4,V3,V5 ,V1,V0,V2,V4,V3,V5,V0,V2,V4,V3,V0,V2,

7、V4,V0,V2,S=V0,V1,V5,V3,V4,V2,Vj,V5,V4,V3,V2,V1,i=5,i=4,i=3,i=2,i=1,D 终点,2022年11月16日星期三,第13页,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk。,V0和k之间存在弧,V0和k之间不存在弧,其中的最小值即为最短路径的长度。,2022年11月16日星期三,第14页,求每一对顶点之间的最短路径,弗洛伊德算法的基本思想是：,从 vi 到

8、vj 的所有可能存在的路径中，选出一条长度最短的路径。,2022年11月16日星期三,第15页,若存在，则存在路径vi,vj / 路径中不含其它顶点若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1若vi,v2, v2,vj存在， 则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 ,依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。,问题描述： 已知一个各边权值均大于 0 的带权有向图，对每对顶点 vivj，要求求出每一对顶点之间的最短路径和最短路径长度。 解决方案： 1. 每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样

9、，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。,弗洛伊德算法思想： 假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为aij的路径，该路径不一定是最短路径，尚需进行n次试探。 首先考虑路径（Vi,V0,Vj）是否存在（即判别（Vi,V0）、（V0,Vj）是否存在）。如存在，则比较（Vi,Vj）和（Vi,V0,Vj）的路径长度，取长度较短者为从 Vi到Vj 的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点 V1，依次类推。可同时求得各对顶点间的最短路径。,定

10、义一个n阶方阵序列D(-1),D(0),D(1),D(2),D(k),D(n-1)其中： D(-1)ij= aij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 0kn-1可见，D(1)ij就是从vi到vj的中间顶点的序号不大于1的 最短路径的长度; D(k)ij就是从vi到vj的中间顶点的序号不大于k的 最短路径的长度; D(n-1)ij就是从vi到vj的最短路径的长度。,各顶点间的最短路径及其路径长度,最短路径弗洛伊德举例,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,P(2),P(1),P(0),P(-1),P,2,1,0,2,1,0,2,

11、1,0,2,1,0,2,1,0,D(2),D(1),D(0),D(-1),D,最短路径导航查询系统(图)设计一个交通导航质询系统，能让旅客质询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。,该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。此程序规定： 1.把城市交通线路转化为图，从而对图进行相应的结构存储； 2.程序的输出信息主要为：起始城市到目的城市的最短路径；3.程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；,

12、概要设计 对于这样的问题，先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲丙相距7千米，且只有从甲到丙的单程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千米，且只有从己到丙的单程线路。编程出能求出个一点到任一点的最短路经。,则图G的邻接矩阵为： 甲 乙 丙 丁 戊 己 甲 7 4 乙 2 8 丙 5 丁 3 3

13、 2 戊 6 己 6 ,系统用到的数据有： int which;int v ;int endv;用到的主要函数： 1）void DispMat(MGraph g) /输出邻接矩阵g2）void ppath(int pathMAXV,int v,int endv) /输出相应选择的起点和终点的最短路3）void DisPath(int AMAXV,int pathMAXV,int n,int v,int endv)/由path计算最短 路径,4）void Floyd(MGraph g,int v,int endv) /采用弗洛伊德算法求没对顶点之间的最短 路径5）int main（） /主函数各

14、程序模块之间的调用关系：函数3）可以调用函数2）。 函数4）可以调用函数3）。函数5）可以调用函数1）和函数4）。 （具体程序略）,首先运行程序，包括三个选项，a.需要求最短路径请按：1. b.输出有向图G的邻接矩阵：2. c.退出系统请按：3 .然后可以根据不同的需要选择不同的选项进行操作最后按3退出程序。,测试丁和己,2022年11月16日星期三,第29页,拓扑排序,问题:,假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。,检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。,2022年11月16日星期三,第30页,何谓“拓扑排序”？,对有向图进行如下操作：

15、,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。AOV（Activity On Vertex）网:就是顶点代表活动，边（狐）表示活动的优先关系的有向图。,2022年11月16日星期三,第31页,例如：对于下列有向图,B,D,A,C,可求得拓扑有序序列： A B C D 或 A C B D,2022年11月16日星期三,第32页,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,施工从活动 a1、 a2开始，到达活动 a8和 a9时，整个施工结束。这类有向图中，顶点表示

16、活动，弧表示活动 ai优先于活动 aj ，称这类有向图为顶点表示活动的网（AOV网）。,AOV网(Activity on vertex network) 一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。如图：,AOV网可解决如下两个问题：（1）判定工程的可行性。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中的先后顺序 称这种先后顺序为拓扑有序序列。,如图有如下拓扑有序序列： a1 a2 a3a4 a5 a6 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8,2022年11月16日星期三,第35页,如何进行拓扑排序？,一、从有向

17、图中选取一个没有前驱 的顶点，并输出之；,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,二、从有向图中删去此顶点以及所 有以它为尾的弧；,2022年11月16日星期三,第36页,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点 入度为零的顶点,删除顶点及以它为尾的弧 弧头顶点的入度减1,由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑： 能容易得到各顶点的入度； 有利于寻找任一顶点的所有直接后继。为此，采用邻接表作为AOV网的存储结构，并在头结点中增加一个存放顶点入度的域（

18、indegree）,2022年11月16日星期三,第38页,取入度为零的顶点v;while (v0) printf(v); +m; w:=FirstAdj(v); while (w0) inDegreew-; w:=nextAdj(v,w); 取下一个入度为零的顶点v;if mn printf(“图中有回路”);,算法描述,2022年11月16日星期三,第39页,为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。,CountInDegree(G,indegree); /对各顶点求入度InitStack(S);for ( i=0; iG.vexnum; +i)

19、if (!indegreei) Push(S, i); /入度为零的顶点入栈,2022年11月16日星期三,第40页,count=0; /对输出顶点计数while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegree(w); / 弧头顶点的入度减一 if (!indegreew) Push(S, w); /新产生的入度为零的顶点入栈 if (countG.vexnum) printf(“图中有回路”),将表转换成图,拓扑序列：c1,c9,c4,c2,c12,

20、c10,c11,c5,c3,c6,c7,c8,拓扑序列：c1,c9,c4,c2,c12,c10,c11,c5,c3,c6,c7,c8,拓扑序列：c1,c9,c4,c2,c12,c10,c11,c5,c3,c6,c7,c8,拓扑序列：c1,c9,c4,c2,c10,c11,c12,c5,c3,c6,c7,c8,拓扑序列：c1,c9,c4,c2,c10,c11,c12,c5,c3,c6,c7,c8,拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8,拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8,拓扑序列：c1,c9,c4

21、,c2,c10,c11,c3,c12,c6,c5,c7,c8,拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8,2022年11月16日星期三,第52页,关键路径,问题:,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。,一、AOE网可解决如下问题：估算工程的最短工期（从源点到 汇点至少需要多少时间）找出哪些活动是影响整个工程进展的关键,有4个事件：V1， V2， V3， V5V1为源点，V5为汇点有4个活动：a1, a2, a4, a5V3表示：a2已完成，a5

22、可以开始,二、关键路径几个术语路径长度：路径上各活动持续时间的总和 （即：路径上所有弧的权值之和）关键路径：从源点到汇点之间路径长度最长的路径 （不一定唯一）事件V i的最早发生时间ve(i)：从源点到V i的最长路径长度活动 ai的最早开始时间e(i)：等于该活动的弧尾事件V j的最早发生时间 即若表示活动ai ，则有e(i)=ve(j),ai,事件 vk 的最迟发生时间 vl(k)：是在不推迟整个工期的前提下，该事件最迟必须发生的时间活动ai的最迟开始时间L(i)：是该活动的弧头事件的最迟发生时间与该活动的持续时间之差， 即L(i)=vl(k)- ai 的持续时间关键活动：l(i)=e(i

23、)的活动,由此可见：在AOE网中找关键活动问题可转化为求 l(i)=e(i)，而e(i)=ve(j) l(i)=vl(k) - ai 的持续时间 因此，需先求出事件 的最早、最迟发生时间,关键路径,三、关键路径算法思想1. 从ve(1)=0 开始利用下面递推公式，计算出各事件的最早发生时间ve(j)=Maxve(i)+dut()， j=2, , n ， T其中：T是所有以j为头的弧集合dut()表示活动的持续时间前例中，ve(5)=Maxve(2)+dut()， ve(3)+dut() =Max6+1,4+1=7,2. 从vl(n)=ve(n)开始，利用下面递推公式，计算出各事件的最迟发生时间

24、：vl(i)=Minvl(j)-dut() i=n-1 , , 2 , 1 , S其中：S是所有以i为尾的弧集合,关键路径,关键路径,3. 设活动ai由弧表示，其持续时间为dut()，则利用下面公式，计算出各活动的最早、最迟开始时间：e(i)=ve(j)l(i)=vl(k)-dut()4. 找出e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为关键路径,j,k,ai=dut(),四、例子,关键路径上的活动都是关键活动。缩短非关键活动都不能缩短整个工期 如a6缩短为1，则整个工期仍为8。 又如a6推迟3天开始，或拖延3天完成 （a6=6）均不影响整个工期,分析关键路径

25、的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。 如a7缩短为1，则整个工期为7。 此时，再缩短任一关键活动均不能缩短整个工期。 即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期,最早发生时间vei,最迟发生时间vli,顶点序号vi,最早发生时间vei,最迟发生时间vli,顶点序号vi,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,最早发生时间vei,最迟发生时间vli,顶点序号vi,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7

26、,a10=2,a11=4,0,0,6,6,5,0,4,6,7,7,7,8,16,16,18,18,14,14,ei=vejLi=vlk-dut,2022年11月16日星期三,第65页,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,又例如:,“关键活动”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。,整个工程完成的时间为：从有向图的源点到汇点的最长路径。,源点,汇点,6,1,7,4,2022年11月16日星期三,第66页,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,0,0,0,0,0,0,0,0,0,6,4,5,

27、7,11,5,7,15,14,18,18,18,18,18,18,18,18,18,18,16,14,8,6,6,10,8,0,7,拓扑有序序列: a - d - f - c - b - e - h - g - k,2022年11月16日星期三,第67页,0,6,4,5,7,7,15,14,18,18,14,16,10,7,8,6,6,0,0,0,0,6,4,5,7,7,7,15,14,14,16,0,2,3,6,6,8,8,7,10,2022年11月16日星期三,第68页,算法的实现要点:,显然，求ve的顺序应该是按拓扑有序的次序；,而 求vl的顺序应该是按拓扑逆序的次序；,因为 拓扑逆序序

28、列即为拓扑有序序列的 逆序列，,因此 应该在拓扑排序的过程中， 另设一个“栈”记下拓扑有序序列。,下表给出了某工程各工序之间的优先关系和各工序所需的时问（其中“一”表示无先驱工序），请完成以下各题：(1) 画出相应的AOE网。(2) 列出各事件的最早发生时间和最迟发生时间。(3) 求出关键路径并指明完成该工程所需的最短时间。,实例,试题考核AOE网和关键路径问题。要求熟悉AOE网的概念和如何求关键路径的方法及步骤。(1) 根据表的数据，可得AOE网，如图所示。,(2) 所有事件的最早发生时间ve，如下所示：ve（v1） 0，ve（v2） 3，ve（v3） 2 ve（v4） Max ve（v2）

29、+2，ve（v3）+4 6 ve（v5） ve（v2）3 6， ve（v6） Max ve（v3）+3，ve（v4）+2， ve（v5）+1 8 所有事件的最迟发生时间vl，如下所示：vl（v6） 8， vl（v5）vl（v6）1 7 vl（v4）vl（v6）2 6，vl（v3） Min vl（v4）4，vl（v6）3 2,vl（v2） Min vl（v4）2，vl（v5）3 4vl（v1） Min vl（v2）3，vl（v3）2 0(3) 求所有活动的最早发生时间e、最迟发生时间l和时间余量l-e。e（A）ve（v1） 0 l（A）vl（v2）3 1 l（A）e（A） 1e（B）ve（v1）

30、 0 l（B）vl（v3）2 0 l（B）e（B） 0e（C）ve（v2） 3 l（C）vl（v4）2 4 l（C）e（C） 1e（D）ve（v2） 3 l（D）vl（v5）3 4 l（D）e（D） 1e（E）ve（v3） 2 l（E）vl（v4）4 2 l（E）e（E） 0,e（F）ve（v3） 2， l（F）vl（v6）3 5，l（F）e（F） 3，e（G）ve（v4） 6， l（G）vl（v6）2 6，l（G）e（G） 0，e（H）ve（v5） 6，l（H）vl（v6）1 7， l（H）e（H） 1所以，关键路径为：B、E、G。完成该工程最少需要8天时间。,项目管理关键路径,某项目共有7

31、项活动，其活动顺序、时间、直接费用等见下表。该项目的间接费用为每周1000元。现需要用节点法画出项目的网络图，找出关键线路，并按项目总费用最低的要求优化项目工期,第一步，画出网络图,A6,B3,C8,E5,D4,F7,G2,1,6,7,9,7,14,10,13,10,14,15,21,22,23,23,22,21,15,21,17,14,11,14,7,10,8,6,1,第二步：找出关键线路。本项目共有三条线路：A B E G, 16周；A B D F G, 22周；A C F G, 23周。所以第三条线路（A C F G）为关键线路，如图中红线所示。第三步：计算各活动的赶工单位成本（直接成本

32、）：A: (7-5)(6-5) = 2；B: 0.5；C: 0.75；D: 2；E: 1.5；F: 0.667；G: 2。,第四步：压缩关键线路上的活动F(赶工费率小于1的最小者)，时间由7周压缩至4周，第三条线路的总时间由23周缩短至20周。此时，需重新确定关键线路。第二条线路的时间由22周缩短至19周，第一条线路的时间不变。所以关键线路不变。压缩后的总成本节约为：3000 （间接成本减少） 2000（直接成本增加）= 1000元。,第五步：继续压缩关键线路上的活动C。由于第二条线路只比第三条线路少一周，所以只能压缩一周。重新计算关键线路。第二、三条线路都是关键线路。本次压缩导致的总成本节约为：1000 0.751000 = 250元。第六步：还能压缩吗？现在有可能被压缩的活动是B和C （在关键线路上且时间成本敏感度小于1）。由于它们分别在两条关键线路上，只有同时压缩才有意义。但两项活动的赶工费率之和为1.25，大于1。所以，从项目总成本最小的角度来说，项目工期已经不能再压缩了。第七步：所以，项目总成本最优时的总工期为19周。此时的项目总成本为63000 1000 250 = 61750元。,小结 带权有向图的最短路径问题。 利用AOV网络的拓扑排序问题； 利用AOE网络的关键路径法；,THE END!,