《《数据结构》最短路径关键路径及其应用解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构》最短路径关键路径及其应用解析ppt课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022年7月28日星期四第1页最短路径、关键路径最短路径、关键路径及其应用及其应用 所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。 最短路径问题+ 求从某个源点到其余各点的求从某个源点到其余各点的最短路径最短路径2022年7月28日星期四第3页 每一对顶点之间的最短路径每一对顶点之间的最短路径2022年7月28日星期四第4页 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本思想的算法的基本思想: 依依最短路径的长度最短路径的长度递增的次序求得递增的次序求得各条路径各
2、条路径源点源点v1其中，从源点到从源点到顶点顶点v的最短路径的最短路径是所有路径中长度最短者。v2 给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始点始点 终点终点 Di 最短路径最短路径V1V2V3V4 V510301001030100106030100106030100105030100(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)(V
3、0, V4)(V0, V5)(V0, V2)(V0, V4, V3)(V0, V4)(V0, V5)10503090(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年7月28日星期四第6页 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长
4、度次短的最短路径最短路径的特点：路径长度最短的最短路径最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。2022年7月28日星期四第7页其余最短路径的特点：再下一条路径长度次短的最短路径最短路径的特点: 它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。 它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。如何在计算机中如何在计算机中求得最短路径？求得最短路径？202
5、2年7月28日星期四第9页求最短路径的迪杰斯特拉算法：一般情况下，Distk = 或者 = + 。 设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。 Dijkstra Dijkstra提出了一个按路径提出了一个按路径“长度长度”递增的递增的次序，逐步得到由给定源点到图的其余各点间的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：最短路径的算法：n假设我们以邻接矩阵假设我们以邻接矩阵costcost表示所研究的有向网。表示所研究的有向网。n迪杰斯特拉算法需要一个顶点集合，初始时集合内迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个
6、源点只有一个源点V V0 0 ，以后陆续将已求得最短路径的顶，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为就结束了。集合可用一维数组来表示，设此数组为S S，凡在集合，凡在集合S S以外的顶点，其相应的数组元素以外的顶点，其相应的数组元素Si Si 为为 0 0 ，否则为，否则为 1 1 。n另需一个一维数组另需一个一维数组D D，每个顶点对应数组的一个单元，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值记录从源点到其他各顶点当前的最短路径长度，其初
7、值为为Di=costVDi=costV0 0ii，i=1i=1n n。数组。数组D D中的数据随着算法中的数据随着算法的逐步进行要不断地修改的逐步进行要不断地修改n定义了定义了S S集合和集合和D D数组并对其初始化后，迪杰斯特拉算法数组并对其初始化后，迪杰斯特拉算法在进行中，都是从在进行中，都是从S S之外的顶点集合中选出一个顶点之外的顶点集合中选出一个顶点w w，使使DwDw的值最小。于是从源点到达的值最小。于是从源点到达w w只通过只通过S S中的顶点，中的顶点，把把 w w 加入集合加入集合S S中，并调整中，并调整D D中记录的从源点到集合中中记录的从源点到集合中每个顶点每个顶点v
8、v的距离：的距离： 取取DvDv和和Dw+costwvDw+costwv中值较小的作为新的中值较小的作为新的DvDvn重复上述，直到重复上述，直到S S中包含中包含V V中其余各顶点的最短路径。中其余各顶点的最短路径。 V0 V1 V2 V3 V4 V5 V0 10 30 100V1 5 V2 50 V3 10 V4 20 60 V5 V0 0,V2 2,V4 4,V3 3,V5 5 ,V1 1V0 0,V2 2,V4 4,V3 3,V5 5V0 0,V2 2,V4 4,V3 3V0 0,V2 2,V4 4V0 0,V2 2S=V0 0V1 1V5 5V3 3V4 4V2 2Vj jV5 5V
9、4 4V3 3V2 26030501060V0,4,3,530501090V0,4,53050V0,4,310100V0,530V0,460V0,2,310100V0,530V0,410V0,2V1 1i=5i=4i=3i=2i=1 D 终点终点V0V2V1V4V5V355030101010060202022年7月28日星期四第13页1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk。INFINITYkvarcsGkDi
10、st0.V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。2022年7月28日星期四第14页求每一对顶点之间的最短路径弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。2022年7月28日星期四第15页若存在，则存在路径vi,vj / 路径中不含其它顶点若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1若vi,v2, v2,vj存在， 则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。
11、问题描述：问题描述： 已知一个各边权值均大于已知一个各边权值均大于 0 0 的带权有向图，的带权有向图，对每对顶点对每对顶点 vivjvivj，要求求出每一对顶点之间，要求求出每一对顶点之间的最短路径和最短路径长度。的最短路径和最短路径长度。 解决方案：解决方案： 1. 1. 每次以一个顶点为源点，重复执行迪杰每次以一个顶点为源点，重复执行迪杰斯特拉算法斯特拉算法n n次。这样，便可求得每一对顶点之次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为间的最短路径。总的执行时间为O(nO(n3 3) )。 2. 2. 形式更直接的弗洛伊德（形式更直接的弗洛伊德（FloydFloyd）算法。
12、）算法。时间复杂度也为时间复杂度也为O(nO(n3 3) )。弗洛伊德算法思想：弗洛伊德算法思想： 假设求从顶点假设求从顶点V Vi i到到V Vj j的最短路径。如果从的最短路径。如果从V Vi i到到V Vj j有弧，则从有弧，则从V Vi i到到V Vj j存在一条长度为存在一条长度为aijaij的路的路径，该路径不一定是最短路径，尚需进行径，该路径不一定是最短路径，尚需进行n n次试探次试探。 首先考虑路径（首先考虑路径（V Vi i,V,V0 0,V,Vj j）是否存在（即判别）是否存在（即判别（V Vi i,V,V0 0）、（）、（V V0 0,V,Vj j）是否存在）。如存在，则
13、比）是否存在）。如存在，则比较（较（V Vi i,V,Vj j）和（）和（V Vi i,V,V0 0,V,Vj j）的路径长度，取长度较）的路径长度，取长度较短者为从短者为从 V Vi i到到V Vj j 的中间顶点的序号不大于的中间顶点的序号不大于0 0 的最的最短路径。假如在路径上再增加一个顶点短路径。假如在路径上再增加一个顶点 V V1 1，依依次类推。可同时求得各对顶点间的最短路径。次类推。可同时求得各对顶点间的最短路径。定义一个定义一个n n阶方阵序列阶方阵序列D D(-1)(-1),D,D(0)(0),D,D(1)(1),D,D(2)(2), ,D,D(k)(k), ,D,D(n-
14、1)(n-1)其中：其中： D D(-1)(-1)ij= aijij= aij D D(k)(k)ij=Min Dij=Min D(k-1)(k-1)ij, Dij, D(k-1)(k-1)ik+ Dik+ D(k-1)(k-1)kj kj 0kn-10kn-1可见，可见，D D(1)(1)ijij就是从就是从v vi i到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于1 1的的 最短路径的长度最短路径的长度; ; D D(k)(k)ijij就是从就是从v vi i到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于k k的的 最短路径的长度最短路径的长度; ; D D(n
15、-1)(n-1)ijij就是从就是从v vi i到到v vj j的最短路径的长度。的最短路径的长度。0 4 116 0 23 0各顶点间的最短路径及其路径长度各顶点间的最短路径及其路径长度最短路径弗洛伊德举例最短路径弗洛伊德举例0 4 116 0 23 021CABCABCBCAABCABCABCABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400 320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB 最短路径导航查询系统(图)+设
16、计一个交通导航质询系统，能让旅客质询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。+该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。+此程序规定：+ 1.把城市交通线路转化为图，从而对图进行相应的结构存储；+ 2.程序的输出信息主要为：起始城市到目的城市的最短路径；+3.程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；+概要设计+ 对于这样的问题，先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲
17、丙相距7千米，且只有从甲到丙的单程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千米，且只有从己到丙的单程线路。+编程出能求出个一点到任一点的最短路经。 则图G的邻接矩阵为：+ 甲 乙 丙 丁 戊 己 + 甲 7 4 + + 乙 2 8+ + 丙 5 + + 丁 3 3 2 + + 戊 6 + + 己 6 系统用到的数据有： int
18、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（） /主函数+各程序模块之间的调用关系：+函数3）可以调用函数2）。
19、 +函数4）可以调用函数3）。+函数5）可以调用函数1）和函数4）。 +（具体程序略）+首先运行程序，包括三个选项，+a.需要求最短路径请按：1. +b.输出有向图G的邻接矩阵：2.+ c.退出系统请按：3 .+然后可以根据不同的需要选择不同的选项进行操作+最后按3退出程序。测试丁和己2022年7月28日星期四第29页 拓扑排序拓扑排序 问题问题: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序拓扑排序。2022年7月28日星期四第30页何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作： 按照有向图给出的次
20、序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。AOV（Activity On Vertex）网:就是顶点代表活动，边（狐）表示活动的优先关系的有向图。2022年7月28日星期四第31页例如：对于下列有向图BDAC可求得拓扑有序序列： A B C D 或 A C B D2022年7月28日星期四第32页BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D2022年7月28日星期四第35页如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱没有前驱 的顶点，并输出之； 重复上述两步，直至图空
21、，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所删去此顶点以及所 有以它为尾的弧有以它为尾的弧；2022年7月28日星期四第36页abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减1 2022年7月28日星期四第38页取入度为零的顶点v;while (v0) printf(v); +m; w:=FirstAdj(v); while (w0) inDegreew-; w:=nextA
22、dj(v,w); 取下一个入度为零的顶点v;if mn printf(“图中有回路”);算法描述算法描述2022年7月28日星期四第39页 为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存“入度为零”的顶点。CountInDegree(G,indegree); /对各顶点求入度InitStack(S);for ( i=0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入度为零的顶点入栈2022年7月28日星期四第40页count=0; /对输出顶点计数while (!EmptyStack(S) Pop(S, v); +count;
23、printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegree(w); / 弧头顶点的入度减一 if (!indegreew) Push(S, w); /新产生的入度为零的顶点入栈 if (countG.vexnum) printf(“图中有回路”)课程编号课程名称必要的先修课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析和设计C3，C4C6计算机组成原理C11C7编译原理C3，C5C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C1，C9，C10c1c9
24、c4c2c12c10c11c5c3c6c7c8将表转换成图c1c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11c12c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11c12c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6c5c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12
25、,c6c5c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8c1c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c82022年7月28日星期四第52页 关键路径关键路径问题问题: 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。一、一、AOE网可解网可解决如下问题：决如下问题：+估算工程的最估算工程的最短工期（从源短工期（从源点到点到 汇点至少汇点至少需要多少时间）需要多少
26、时间）+找出哪些活动找出哪些活动是影响整个工是影响整个工程进展的关键程进展的关键a1=6a4=1a2=4a5=1二、关键路径几个术语二、关键路径几个术语路径长度路径长度：路径上各活动持续时间的总和路径上各活动持续时间的总和 （即：路径上所有弧的权值之和即：路径上所有弧的权值之和）关键路径关键路径：从源点到汇点之间路径长度最长的从源点到汇点之间路径长度最长的路径路径 （不一定唯一不一定唯一）事件事件V i的最早发生时间的最早发生时间ve(i)：从源点到从源点到V i的最的最长路径长度长路径长度活动活动 ai的最早开始时间的最早开始时间e(i)：等于该活动的弧尾等于该活动的弧尾事件事件V j的最早
27、发生时间的最早发生时间 即若即若表示活动表示活动ai ，则有，则有e(i)=ve(j)vjvkai+事件事件 vk 的最迟发生时间的最迟发生时间 vl(k)：是在不推迟整个工是在不推迟整个工期的前提下，该事件最迟必须发生的时间期的前提下，该事件最迟必须发生的时间+活动活动ai的最迟开始时间的最迟开始时间L(i)：是该活动的弧头事件是该活动的弧头事件的最迟发生时间与该活动的持续时间之差，的最迟发生时间与该活动的持续时间之差， 即即L(i)=vl(k)- ai 的持续时间的持续时间+关键活动：关键活动：l(i)=e(i)的活动的活动 关键路径三、关键路径算法思想三、关键路径算法思想1. 从从ve(
28、1)=0 开始利用下面递推公式，计开始利用下面递推公式，计算出各事件的最早发生时间算出各事件的最早发生时间ve(j)=Maxve(i)+dut()， j=2, , n ， TT其中：其中：T T是所有以是所有以j j为头的弧集合为头的弧集合dut()dut()表示活动的持续时间表示活动的持续时间前例中，前例中，ve(5)=Maxve(2)+dut()ve(5)=Maxve(2)+dut()， ve(3)+dut()ve(3)+dut() =Max6+1,4+1=7 =Max6+1,4+1=7a1=6a4=1a2=4a5=12. 从从vl(n)=ve(n)开始，利用下面递推公式，开始，利用下面递
29、推公式，计算出各事件的最迟发生时间：计算出各事件的最迟发生时间：vl(i)=Minvl(j)-dut() i=n-1 , , 2 , 1 , SS其中：其中：S S是所有以是所有以i i为尾的弧集合为尾的弧集合关键路径 关键路径3. 设活动设活动ai由弧由弧表示，其持续时间为表示，其持续时间为dut()，则利用下面公式，计算出各活动，则利用下面公式，计算出各活动的最早、最迟开始时间：的最早、最迟开始时间：e(i)=ve(j)l(i)=vl(k)-dut()4. 找出找出e(i)=l(i)的活动，即为关键活动，诸关的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为键活动组成的从源点到汇
30、点的路径即为关键关键路径路径四、例子四、例子+关键路径上的活动都是关键活动。关键路径上的活动都是关键活动。+缩短非关键活动都不能缩短整个工期缩短非关键活动都不能缩短整个工期 如如a6缩短为缩短为1，则整个工期仍为，则整个工期仍为8。 又如又如a6推迟推迟3天开始，或拖延天开始，或拖延3天完成天完成 （a6=6）均不影响整个工期）均不影响整个工期+分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。 如a7缩短为1，则整个工期为7。 此时，再缩短任一关键活动均不能缩短整个工期。 即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期v1v
31、3v4v5v6v7v8v2v9最早发生时间vei最迟发生时间vli顶点序号viv1v3v4v5v6v7v8v2v9最早发生时间vei最迟发生时间vli顶点序号via2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v3v4v5v6v7v8v2v9最早发生时间vei最迟发生时间vli顶点序号via2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4006650467778161618181414ei=vejLi=vlk-dut2022年7月28日星期四第65页abcdefghk64521187244又例如又例如:
32、:“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。源点汇点61742022年7月28日星期四第66页abcdefghk64521187244a b c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列: a - d - f - c - b - e - h - g - k2022年7月28日星期四第67页a b c d efg h kvevl06457715 14 18
33、1814161078660ab ac ad be ce df eg eh fh gk hk权权6 4 5 1 1 2 8 7 4 2 4el000645777 15 14141602366887 102022年7月28日星期四第68页 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序； 而 求vl的顺序应该是按拓扑逆序拓扑逆序的次序；因为 拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此 应该在拓扑排序的过程中， 另设一个“栈栈”记下拓扑有序序列。+下表给出了某工程各工序之间的优先关系和各工序所需的时问（其中“一”表示无先驱工序），请完成以下各题：+(1) 画出
34、相应的AOE网。+(2) 列出各事件的最早发生时间和最迟发生时间。+(3) 求出关键路径并指明完成该工程所需的最短时间。实例工序代号工序代号所需时间所需时间先驱工序先驱工序A3B2C2AD3AE4BF3AG2C、EH1D+试题考核AOE网和关键路径问题。要求熟悉AOE网的概念和如何求关键路径的方法及步骤。+(1) 根据表的数据，可得AOE网，如图所示。+ (2) 所有事件的最早发生时间ve，如下所示：+ve（v1） 0 ，ve（v2） 3 ，ve（v3） 2 +ve（v4） Max ve（v2）+2，ve（v3）+4 6 +ve（v5） ve（v2）3 6 ， +ve（v6） Max ve（v
35、3）+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 4+vl（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） 1+e（B）ve（v1） 0 l（B）vl（v3）2 0 l（B）e（B） 0+e（C）ve（v2
36、） 3 l（C）vl（v4）2 4 l（C）e（C） 1+e（D）ve（v2） 3 l（D）vl（v5）3 4 l（D）e（D） 1+e（E）ve（v3） 2 l（E）vl（v4）4 2 l（E）e（E） 0e（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项活动，其活动顺序、时间、直接费用等见下表
37、。该项目的间接费用为每周1000元。现需要用节点法画出项目的网络图，找出关键线路，并按项目总费用最低的要求优化项目工期活活动动代代号号前置活前置活动动活动时间（周）活动时间（周）活动直接费用（千元）活动直接费用（千元）正常正常时间时间赶工后赶工后时间时间正常直正常直接费接费赶工后直赶工后直接费接费A 6557BA3145CA8469DB4335EB53811FC, D741012GE, F2146第一步，画出网络图第一步，画出网络图A6B3C8E5D4F7G216797141013101415212223232221152117141114710861+第二步：找出关键线路。本项目共有三条线路
38、：A B E G, 16周；A B D F G, 22周；A C F G, 23周。所以第三条线路（A C F G）为关键线路，如图中红线所示。+第三步：计算各活动的赶工单位成本（直接成本）：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（直接
39、成本增加）= 1000元。+第五步：继续压缩关键线路上的活动C。由于第二条线路只比第三条线路少一周，所以只能压缩一周。重新计算关键线路。第二、三条线路都是关键线路。本次压缩导致的总成本节约为：1000 0.751000 = 250元。+第六步：还能压缩吗？现在有可能被压缩的活动是B和C （在关键线路上且时间成本敏感度小于1）。由于它们分别在两条关键线路上，只有同时压缩才有意义。但两项活动的赶工费率之和为1.25，大于1。所以，从项目总成本最小的角度来说，项目工期已经不能再压缩了。+第七步：所以，项目总成本最优时的总工期为19周。此时的项目总成本为63000 1000 250 = 61750元。小结小结 带权有向图的最短路径问题。 利用AOV网络的拓扑排序问题； 利用AOE网络的关键路径法； THE END!