下载文档原格式
最短路径知识点总结最短路径问题的核心思想是通过某种策略找到两个节点之间的最短路径。
在图的表示方法上，最短路径问题通常使用邻接矩阵或邻接表来表示图的结构。
多种最短路径算法也可以适用于不同的图模型，包括有向图、无向图、带权图等。
常用的最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。
下面将对这些算法进行介绍和总结。
Dijkstra算法是一种解决单源最短路径问题的贪心算法。
它的核心思想是通过不断地确定距离源点距离最短的顶点来逐步扩展已知的最短路径集合。
具体步骤包括：初始化距离数组，设置起点距离为0，其他顶点距离为无穷大；选择未访问顶点中距离最短的顶点，并将其标记为已访问；更新与该顶点相邻的顶点的距离；不断重复以上步骤直到所有顶点都被访问。
Dijkstra算法的时间复杂度为O(V^2)，其中V表示顶点的个数。
当图比较大时，可以使用堆优化的Dijkstra算法，将时间复杂度优化到O((V+E)logV)。
Bellman-Ford算法是一种解决单源最短路径问题的动态规划算法。
它的核心思想是通过对所有边进行松弛操作，不断更新顶点的最短路径估计值。
具体步骤包括：初始化距离数组，设置起点距离为0，其他顶点距离为无穷大；循环遍历所有边，不断进行松弛操作，直到没有发生变化为止。
Bellman-Ford算法的时间复杂度为O(VE)，其中V表示顶点的个数，E表示边的个数。
这个算法可以解决包含负权边的图的最短路径问题，而Dijkstra算法则无法处理负权边。
Floyd-Warshall算法是一种解决多源最短路径问题的动态规划算法。
它的核心思想是通过对所有顶点之间的距离进行不断更新，找到所有顶点之间的最短路径。
具体步骤包括：初始化距离矩阵，设置顶点之间的距离为边的权重，若没有直接相连的边则设置为无穷大；循环遍历所有顶点，尝试将每个顶点作为中转点，并尝试更新所有顶点对之间的距离。
为什么关键路径等于最短时间最短路径计算案例这是一篇关于关键路径和最短时间最短路径计算的深度探讨文章，我将从简到繁，由浅入深地解释这个主题，并据此撰写一篇有价值的文章。
文章将采用知识的文章格式，内容会使用序号标注，并多次提及指定的主题文字。
我的个人观点和理解也会在文章中得到充分体现。
我们需要了解什么是关键路径和最短时间最短路径计算。
关键路径是项目管理中的一个重要概念，它指的是项目中的一条或多条路径，如果这些路径上的活动延迟一天，就会导致整个项目的延迟。
而最短时间最短路径计算则是指在一个加权有向图中，从一个顶点到另一个顶点的最短路径问题。
接下来，我们将深入探讨为什么关键路径等于最短时间最短路径计算，并且结合实际案例来说明。
这样的深度和广度的探讨，将帮助我们更全面地理解这个主题。
在这个讨论中，我认为关键路径等于最短时间最短路径计算是因为项目管理中的关键路径实际上就是项目中的最短路径。
通过案例分析，我们可以更加具体地理解这个概念。
比如某个项目中有许多任务需要完成，每个任务都有其完成所需的时间和依赖关系，我们需要找到一条路径，使得这些任务能够在最短的时间内完成。
这个路径就是项目的关键路径，也可以看作是最短时间最短路径。
在文章结尾的总结和回顾性内容中，我将再次强调关键路径和最短时间最短路径计算的重要性，并提出自己对这个主题的个人观点和理解。
总字数会超过3000字，以确保文章的深度和广度。
通过这篇文章，我希望读者能够对关键路径和最短时间最短路径计算有更深入的理解，从而在实际项目管理中能够更加灵活地应用这些概念，提高项目的执行效率和质量。
在实际项目管理中，关键路径和最短时间最短路径计算是非常重要的工具和技术。
它们可以帮助项目经理和团队有效地规划和控制项目进度，确保项目能够按时完成。
在这一部分，我们将进一步讨论关键路径和最短时间最短路径计算的具体应用，并探究如何在实际项目中应用这些概念。
让我们再次强调一下关键路径和最短时间最短路径计算的定义。
关键路径法CPM（CriticalPathMethod关键路径法）是项目管理中最基本也是非常关键的一个概念，它上连着WBS（工作分解结构），下连着执行进度控制与监督。
关键路径是项目计划中最长的路线。
它决定了项目的总实耗时间。
项目经理必须把注意力集中于那些优先等级最高的任务，确保它们准时完成，关键路径上的任何活动的推迟将使整个项目推迟。
向关键路径要时间，向非关键路径要资源。
所以在进行项目操作的时候确定关键路径并进行有效的管理是至关重要的。
关键路径法关键路径法 - 定义关键路径法Critical Path Method，CPM)，又称关键线路法。
一种计划管理方法。
它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。
它用网络图表示各项工作之间的相互关系，找出控制工期的关键路线，在一定工期、成本、资源条件下获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。
CPM中工序时间是确定的，这种方法多用于建筑施工和大修工程的计划安排。
它适用于有很多作业而且必须按时完成的项目。
关键路线法是一个动态系统，它会随着项目的进展不断更新，该方法采用单一时间估计法，其中时间被视为一定的或确定的。
关键路径法关键路径法 - 起源关键路径法关键路线法是一种网络图方法，最早出现于20世纪50年代，由雷明顿-兰德公司(Remington- Rand)的JE克里(JE Kelly)和杜邦公司的MR沃尔克(MR Walker)在1957年提出的，用于对化工工厂的维护项目进行日程安排。
这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。
关键路径法关键路径法 - 原理与网络图设定步骤关键路径法关键路径法（CPM）是一种网络分析技术，是确定网络图当中每一条路线从起始到结束，找出工期最长的线路，也就是说整个项目工期的决定是由最长的线路来决定的。
关键路径和最短路径：基本思路：1.关键路径法：关键路径法对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径。
2.最短路径法：求一个顶点到其余顶点的最短路径主要运用Dijkstra 算法，把图中的顶点分为两个集合S 和T ，集合S 皴法已确定最短路径的顶点，集合T 存放尚未确定最短路径的顶点。
按最短路径长度递增的次序逐个将T 集合中的顶点加入到S 中，直到从源点出发可以到达的所有顶点都在S 中为止。
演算过程：1.关键路径各项活动的最早时间，t(A)=0t(B)=max{2,15+4}=19t(C)=15t(D)=19+10=29t(E)=max{19+19,15+11}=38t(F)=max{29+6,38+5}=43事项的最早时间为43各事项的最迟时间，t(F)=43t(D)=43-6=37t(E)=43-5=38t(B)=min{37-10,38-19}=19t(C)=min{19-4,38-11}=15t(A)=15-15=0.所以关键路径为：A →C →B →E →FA B C DE F 2 1111 465起终2.最短路径首先将A 点分到S集合中，其余各点分到T集合，S（A）=0，其余各点为T=+∞与A相关的边（A,B）,(A,C)T(B)=min{T(B),S(A)+2}=min{+∞，0+2}=2T(C)=min{T(C),S(A)+15}=min{+∞,0+15}=15∴S(C)=15,记录路径(A,C)与C相关的边（C,B）,(C,E)T(B)=min{T(B),S(C)+4}=min{2,15+4}=2T(E)=min{T(E),S(C)+11}=min{+∞,15+11}=26∴S(B)=2,记录路径(A,B)与B相关的边(B,D),(B,E)T(D)=min{T(D),S(B)+10}=min{+∞,2+10}=12T(E)=min{T(E),S(B)+19}=min{26,2+19}=21∴S(D)=12，记录路径(B,D)与D相关的边(D,F)T(F)=min{T(F),S(D)+6}=min{+∞，12+6}=18∴S(E)=21，记录路径(B,E)与E相关的边(E,F)T(F)=min{T(F),S(E)+5}=min{18,21+5}=18∴S(F)=18，记录路径(D,F)从A点到到其余各顶点最短路为：所以A到F的最短路为A→B→D→FB+树和B*树：针对上述文件建立4阶的B+树和B*树索引结构，用图形描述在该文件中先后新增ID为50和45的记录，用图形分别描述新增两条记录后索引结构（B+树和B*树）的变化B+树和B*树的区别：B+叶子结点中存储记录,在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。
数据结构课程辅导---图的最短路径、拓扑排序和关键路径一、最短路径由图的概念可知，在一个图中，若从一顶点到另一顶点存在着一条路径(这里只讨论无回路的简单路径)，则称该路径长度为该路径上所经过的边的数目，它也等于该路径上的顶点数减1。
由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。
上面所述的图的最短路径问题只是对无权图而言的，若图是带权图，则把从一个顶点i到图中其余任一个顶点j的一条路径上所经过边的权值之和定义为该路径的带权路径长度，从vi到vj可能不止一条路径，我们把带权路径长度最短（即其值最小）的那条路径也称作最短路径，其权值也称作最短路径长度或最短距离。
例如，在图3-1中，从v0到v4共有三条路径：{0,4},{0,1,3,4}和{0,1,2,4}，其带权路径长度分别为30,23和38，可知最短路径为{0,1,3,4}，最短距离为23。
图3-1 带权图和对应的邻接矩阵实际上，这两类最短路径问题可合并为一类，这只要把无权图上的每条边标上数值为1的权就归属于有权图了，所以在以后的讨论中，若不特别指明，均认为是求带权图的最短路径问题。
求图的最短路径问题用途很广。
例如，若用一个图表示城市之间的运输网，图的顶点代表城市，图上的边表示两端点对应城市之间存在着运输线，边上的权表示该运输线上的运输时间或单位重量的运费，考虑到两城市间的海拔高度不同，流水方向不同等因素，将造成来回运输时间或运费的不同，所以这种图通常是一个有向图。
如何能够使从一城市到另一城市的运输时间最短或者运费最省呢？这就是一个求两城市间的最短路径问题。
求图的最短路径问题包括两个方面：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。
下面分别进行讨论。
1. 从一顶点到其余各顶点的最短路径对于一个具有n个顶点和e条边的图G，从某一顶点vi(称此为源点)到其余任一顶点vj(称此为终点)的最短路径，可能是它们之间的边(i,j)或<i,j>，也可能是经过k个（1≤k≤n-2，最多经过除源点和终点之外的所有顶点）中间顶点和k+1条边所形成的路径。
第四节最短路径与关键路径1．最短路径：对于图G＝<V, E>(有向图或无向图)的每一条边e都附加一个实数w(e)，w(e)称为e的权，则称G是一个带权图或赋权图，并把它记作G＝<V , E, w >，其中w是E上的实函数，叫作权函数。
对于简单图，当 e =(v i ,v j )（或<v i ,v j >），常把w(e) 记作w ij。
设G＝<V , E, w >是n阶简单带权图（无向的或有向的），边（v i ,v j）（或<v i ,v j >）的权为w ij，并且约定：w ii = 0;当v i与v j之间无边关联时w ij＝∞。
G中一条通路（回路）上各条边的权之和叫作该通路（回路）的权。
G中从v i到v j的权最小的通路叫作v i到v j的最短路径。
根据刚才的约定，若不存在从v i到v j的通路，则认为v i到v j的最短路径的权为∞。
所谓最短路径问题就是求给定图中两点之间的最短路径。
下面介绍求最短路径问题的Dijkstra标号法。
它仅可用于所有的权w ij ≥ 0的情况，可以求从给定顶点（设为v1）到所有顶点的最短路径。
先介绍几个符号和名词。
（1）设l i(r)∗为顶点v1（最短路径的起点）到v i（最短路径的终点）的最短路径的权。
若v i获得li(r)∗，称v i在第r(r ≥ 0)步获得了永久性标号，简称为p标号。
由于v1为起点，且w＝0，故当r = 0时，l1(0)∗= 0，首先v1获得永久性标号P。
11（2）设l(jr)为v1到v j的最短路径的权在第r步获得的一个上界，称l(jr)为顶点v j的临时性标号，简称t标号，其中，r ≥ 0，开始的时候，l j = w1j。
(0)（3）设P r = {v v在前r步获p标号}，称P r为第r步的通过集，r ≥ 0。
（4）设T r =V −P r，称T r为第r步未通过集。
Dijkstra标号法的计算步骤如下：（1）开始令r ← 0，获p标号：l1(0)∗= 0,P0 ={v1},T0 =V −P0,v j( j ≠1)的t标号为l(0)j= w1j （2）求下一个p标号顶点。
详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?1.2 分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。
1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
1.4 解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。
1、求下图从事件0出发的关键路径，要求详细过程。
1、事件Vj可能的最早发生时间ve(j)V e(0)=0;V e(1)=ve(0)+weight(<v0,v1>)=0+5=5;V e(2)=ve(0)+weight(<v0,v2>)=0+9=9;V e(3)=ve(0)+weight(<v0,v3>)=0+14=14;V e(4)=ve(1)+weight(<v1,v4>)=5+4=9;V e(5)=max{ve(2)+weight(<v2,v5>),ve(4)+weight(<v4,v5>)}=max{9+10,9+6}=19;V e(6)=ve(3)+weight(<v3,v6>)=14+3=17;V e(7)=max{ve(3)+weight(<v3,v7>),ve(6)+weight(<v6,v7>)}=max{14+7,17+5}=22; V e(8)=max{ve(6)+weight(<v6,v8>),ve(7)+weight(<v7,v8>)}=max{17+5,22+8}=30; V e(9)=max{ve(4)+weight(<v4,v9>),ve(5)+weight(<v5,v9>),ve(8)+weight(<v8,v9>)}= Max{9+12,19+10,30+18}=48;2、事件vi可能的最晚发生时间vl(i)Vl(9)=48;Vl(8)=vl(9)-weight(<v8,v9>)=48-18=30;Vl(7)=vl(8)-weight(<v7,v8>)=30-8=22;Vl(6)=min{ve(7)-weight(<v7,v6>),ve(8)-weight(<v8,v6>)}=min{22-5,30-5}=min{17,25}=17; Vl(5)=vl(9)-weight(<v5,v9>)=48-10=38;Vl(4)=min{vl(5)-weight(<v4,v5>),vl(9)-weight(<v4,v9>)}=min{38-6,48-12}=min{32,36}=32; Vl(3)=min{vl(6)-weight(<v3,v6>),vl(7)-weight(<v3,v7>)}=min{17-3,22-7}=min{14,15}=14 Vl(2)=vl(5)-weight(<v2,v5>)=38-10=28;Vl(1)=vl(4)-weight(<v1,v4>)=32-4=28;Vl(0)=min{vl(1)-weight(<v0,v1>),vl(2)-weight(<v0,v2>),vl(3)-weight(<v0,v3>)}= Min{28-5,28-9,14-14}=min{23,19,0}=0;3、活动a(k)=<vi,vj>的最早开始时间E(k)E(0)=ve(0)=0E(1)=ve(0)=0E(2)=ve(0)=0E(3)=ve(1)=5E(4)=ve(2)=9E(5)=ve(3)=14E(6)=ve(3)=14E(7)=ve(4)=9E(8)=ve(6)=17E(9)=ve(4)=9E(10)=ve(5)=19E(11)=ve(6)=17E(12)=ve(7)=22E(13)=ve(8)=304、活动a(k)的最晚开始时间L(k)L(0)=vl(1)-weight(<v0,v1>)==28-5=23L(1)=vl(2)-weight(<v0,v2>)==28-9=21L(2)=vl(3)-weight(<v0,v3>)==14-14=0L(3)=vl(4)-weight(<v1,v4>)==32-4=28L(4)=vl(5)-weight(<v2,v5>)==38-10=28L(5)=vl(6)-weight(<v3,v6>)==17-3=14L(6)=vl(7)-weight(<v3,v7>)==22-7=15L(7)=vl(5)-weight(<v4,v5>)==38-6=32L(8)=vl(7)-weight(<v6,v7>)==22-5=17L(9)=vl(9)-weight(<v4,v9>)==48-12=36L(10)=vl9)-weight(<v5,v9>)==48-10=38L(11)=vl(8)-weight(<v6,v8>)==30-5=34L(12)=vl(8)-weight(<v7,v8>)==30-8=22L(13)=vl(9)-weight(<v8,v9>)==48-18=30L(0)-E(0)=23-0=23L(1)-E(1)=21-0=21L(2)-E(2)=0-0=0L(3)-E(3)=28-5=23L(4)-E(4)=28-9=19L(5)-E(5)=14-14=0L(6)-E(6)=15-14=1L(7)-E(7)=32-9=23L(8)-E(8)=17-17=0L(9)-E(9)=36-9=27L(10)-E(10)=38-19=19L(11)-E(11)=34-17=17L(12)-E(12)=22-22=0L(13)-E(13)=30-30=05、题中图的关键路径如下图所示：2、对于下图所示的有向图，试利用Dijkstra算法求源点1到其他各顶点的最短路径，可参考教材P207图7.29中的表格形式给出计算过程。
关键路径算法相关概念解读关键路径VS最短路径关键路径算法⼀般会在最短路径算法的后⾯进⾏讲解。
这就需要我们⾸先区分出关键路径算法和最短路径算法在前提上的不同：最短路径算法是找尽可能短的路来保证路径长度最⼩，你只需要找出⼀条最短的路就⾏。
但是在关键路径⾥，⼀个顶点是有多个前提的，只有前提的路径都⾛完，才能发⽣该顶点的事件，那么只有最长的路径⾛完，保证其余短的路都早已经⾛完，该事件才发⽣。
事件和活动在关键路径算法中，我们将事件定义为AOE图中的“顶点”，将活动定义为AOE图中的“弧”。
事件的发⽣和开始这⾥要⾸先弄明⽩的是两个词，也就是后⾯要学到的概念中的 "发⽣" 和 "开始"。
“发⽣”是针对于事件的，也就是图中的顶点。
什么叫事件发⽣了呢？只有在指向该顶点的所有有向边对应的活动结束，该顶点所代表的事件才发⽣。
举个例⼦，⼀个事件C，它仅被两条边a, b指向，仅当a，b两活动都完成时，事件C发⽣。
“开始”是针对于活动的，也就是图中的弧。
只有在⼀个顶点所代表的事件发⽣后，从该顶点出发的所有边对应的活动才能开始。
什么时候开始？即可以在事件⼀完成就⽴马开始接下来的活动，也可以推迟活动开始的时间。
事件的最早发⽣时间（etv）我们前⾯说过，发⽣是针对于事件的，⼀个事件要发⽣，⾸先要指向它的活动都完成。
⼀个事件C，被两个活动a，b指向，a活动的耗费时间是3， b活动的耗费时间是5。
那么看下图，从开始到C事件的发⽣要多久呢？是最⼤路径长度5，因为C事件发⽣的前提必须是a，b两活动完成（活动可同时进⾏）。
C事件只有等到b完成才发⽣，最早完成时间由耗时最久的路决定，所以这就是为什么要取最长路径长度。
因此：事件的最早发⽣时间推导公式：事件的最晚发⽣时间（ltv）最晚发⽣时间的意义是：在不推迟整个⼯程完成的前提下，该事件最晚的发⽣时间。
因此我们可以想象：在⼀个AOE图中的汇点，其最晚发⽣时间和最早发⽣时间⼀定是相同的，因为汇点事件的发⽣事件⼀定会直接决定整个⼯程的完成时间。
数据结构第20次课
（续表）
思考.题
作业题试对下图所示的AOE网络，解答下列问题。
(1) 这个工程最早可能在什么时间结束。
(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。
(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。
(4) 确定哪些活动是关键活动。
画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。
*参考资料《数据结构辅导与提高》，徐孝凯编著，清华大学出版社
《数据结构习题解答与考试指导》，梁作娟等编著，清华大学出版社
授课内容
关键路径
对整个工程和系统，人们关心的是两个方面的问题：
一）工程能否顺利进行（对AOV网进行拓扑排序）
二）估算整个工程的完成所必须的最短时间（对AOE网求关键路径）
1. AOE-网
}
与AOV-网相对应的是AOE-网(Activity On Edge)，即边表示活动的网。
AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活
动，权表示活动持续的时间。
通常，AOE-网可用来估算工程的完成时间。
例：下图是一个假想的有11项活动的AOE-网。
其中有9个事件v
1
，
v
2
，…，v
9
，每个事件表示在它之前的活动已经完成，在它之后的活动可以
开始。
如v
1
表示整个工程开始，v
9
表示整个工程结束，v
5
表示a
4
和a
5
已经
完成，a
7
和a
8
可以开始。
与每个活动相联系的数是执行该活动所需的时间。
比如，活动a
1
需要6天，a
2
需要4天等。
和AOV-网不同，对AOE-网有待研究的问题是：
(1)完成整项工程至少需要多少时间
(2)哪些活动是影响工程进度的关键
2. 关键路径
由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间
是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上
各活动持续时间之和，不是路径上弧的数目)。
路径长度最长的路径叫做关
备注：
回顾
键路径(Critical Path)。
假设开始点是v1，从v1到v i的最长路径长度叫做事件v i的最早发生时间。
这个时间决定了所有以v
i
为尾的弧所表示的活动的最早开始时间。
我
们用e(i)表示活动a
i
的最早开始时间。
还可以定义一个活动的最迟开始时
间l(i)，这是在不推迟整个工程完成的前提下，活动a
i
最迟必须开始进行
的时间。
两者之差l(i)-e(i)意味着完成活动a
i
的时间余量。
我们把l(i)=e(i)的活动叫做关键活动。
显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。
因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
例：上图中从v
1到v
9
的最长路径是(v
1
,v
2
,v
5
,v
8,
v
9
)，路径长度是18，
即v
9
的最早发生时间是18。
解决方案：
]
由上分析可知，辨别关键活动就是要找e(i)=l(i)的活动。
为了求得AOE-网中活动的e(i)和l(i)，首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。
如果活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>),则有如下关系：
e(i ) = ve(j) (1)
l(i) = vl(k)-dut(<j,k>)
求ve(j)和vl(j)需分两步进行：
(1) 从ve(0)开始向前递推
其中，T是所有以第j个顶点为头的弧的结合。
(2) 从vl(n-1)=ve(n-1)起向后递推
其中，S是所有以第i个顶点为尾的弧的集合。
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。
也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。
因此，可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
\
所以，求关键路径的算法：
(1) 输入e条弧（j，k），建立AOE网的存储结构。
(2) 从源点v0出发，令ve[0]＝0按拓扑有序求其余各顶点的最早发生时ve[i](1≤i≤ n-1)。
如得到的拓扑序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。
(3) 从汇点vn出发，令vl[n-1]= ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2 ≥i≥ 2)；
(4) 根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。
若某条弧满足条件e(s)=l(s)，则为关键活动。
计算顶点的ve值是在拓扑排序的过程中进行的。
计算ve需对拓扑排序的算法作如下修改：
(1) 在拓扑排序之前设初值，令ve(i)=0(0<=i<n-1);
(2) 在算法中增加一个计算vj的直接后继vk的最早发生时间的操作：若 ve(j)+dut(<j,k>) > ve(k)，则 ve(k) = ve(j)+dut(<j,k>)；
(3) 为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，则需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的 ve 值之后，从栈顶至栈底便为逆拓扑有序序列。
先将拓扑排序算法改写成算法1，则算法2便为求关键路径的算法。
最短路径
问题背景：
假若要在计算机上建立一个交通咨询系统则可采用图的结构来表示实际的交通网络。
图中顶点表示城市，边表示城市间的交通。
这个咨询系统可以回答旅客提出的各种问题。
来看一简单的图的最短路径问题。
例：一位旅客要从A城到B城，可能希望选择一条途中中转次数最少的，或交通费用最节省的路线；而对于司机来说，里程和速度则是他们感兴趣的。
为了在图上表示有关信息，可对边赋以权，权的值表示两城市间的距离，或途中所需时间，或交通费用等等。
此时路径长度的度量就不再是路径上边的数目，而是路径上边的权值之和。
]
考虑到交通图的有向性(如逆水和顺水的船速就不一样)，本节将讨论带权有向图，并称路径上的第一个顶点为源点，最后一个顶点为终点。
最短路径问题：如果从图中源点出发到达终点的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。
从某个源点到其余各顶点的最短路径
问题描述：给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。
限定各边上的权值大于或等于0。
例：带权有向图G中从v0到其余各顶点之间的最短路径如图所示。
如何在计算机中求得最短路径
迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序，逐步产生最短路径的算法。
首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。
∈V-S) ，则用反证法来证明：假设此路径上有一个顶点不在S中(v
p
说明存在一条终点不在S而长度比此路径短的路径。
但是，这是不可能的。
因为我们是按路径长度递增的次序来产生各最短路径的，故长度比此路径短的所有路径均已产生，它们的终点必定在S中，即假设不成立。
，以后陆Dijkstra算法需一个顶点集合，初始时集合内只有源点V
续将已求得最短路径的顶点加入到集合中，直到全部顶点都进入。
集合可用一维数组S来表示，凡集合S以外的顶点，其相应数组元素S[i]为0，否则为1。
另需一个一维数组dist，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，初值为dist[i]=cost[V0][i]，i=1…n。
数组dist中的数据随着算法的逐步进行要不断地修改。
算法在进行中，都是从S之外的顶点集中选一顶点w，使dist[w]的值最小。
于是从
for(w=0; w<; ++w) //更新当前最短路径及距离
if(!final[w]&&(min+[v][w]<D[w])){ //修改D[w],P[w]
D[w]=min+[v][w];
P[w]=P[v];P[w][w]=TRUE; //P[w]=P[v]+[w] }//if
}//for
}//ShortestPath_DIJ
算法分析：
{
第一个FOR循环的时间复杂度是O(n)，第二个FOR循环共进行n-1次，每次执行的时间是O(n)。
所以总时间复杂度是O(n2)。
人们可能只希望找到从源点到某一个特定的终点的最短路径，但是，这个问题和求源点到其它所有顶点的最短路径一样复杂，其时间复杂度也是O(n2) 。
例：迪杰斯特拉算法。
