数据结构第19讲_关键路径与最短路径_C

第7章
7.1 图的定义和术语 7.2 7.3 7.4 7.5
图
图的存储结构 图的遍历 图的连通性问题 有向无环图及其应用
7.5.1 拓扑排序
7.5.2 关键路径
7.6 最短路径
7.5.2 关键路径
对整个工程和系统，人们关心的是两个方面
的问题：
1）工程能否顺利进行
对AOV网进行拓扑排序
2）估算整个工程完成所必须的最短时间 对AOE网求关键路径
由此可知：辨别关键活动就是找e(i)＝l(i)的活动。
为求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早 发生时间 ve(j)和 最迟发生时间vl(j)。 若活动ai由弧<i,j>表示，持续时间记为dut(<i,j>)， 则有如下关系：
Vi
ai
Vj
活动i的最早开始时间等于事件j的最早发生时间 e(i)＝ ve(i) 活动i的最迟开始时间等于事件k的最迟时间减去活动i 的持续时间 l(i)＝ vl(j) - dut(<i，j>)
公式意义：由从Vi顶点指出的弧所代表的活动中取需最早 开始的一个开始时间作为Vi的最迟发生时间。
由此得到下述求关键路径的算法：
1）输入e条弧<i,j>，建立AOE网的存储结构。 2）从源点v0出发，令ve[0]＝0按拓扑有序求其余各顶点的 最早发生时ve[i]（1≤i≤ n-1）。如果得到的拓扑有 序序列中顶点个数小于网中顶点数n，则说明网中存在
AOE-网

AOE－网(Activity On Edge Network)：即 边表示活动的网。AOE网是一个带权的有向 无环图。其中：

顶点表示事件（Event） 弧表示活动（Activity） 权值表示活动持续的时间
通常可用AOE网来估算工程的完成时间。
v1 表 示 整 个 工 程 的 开 始
1.单源点最短路径 2.所有顶点对之间的最短路径
7.6.1 单源点最短路径
给定带权有向图G和源点v, 求从v到G中其余 各顶点的最短路径。
V5
10
100
60
V0 V1
5
30
始点 终点
D[i]
∞
最短路径
(V0, V2)
(V0, V4, V3) 2 (V0, V4) (V0,(V4, 4, 5)5)5) (V0, 0 V3, V VV V
求ve(j)和 vl(j)需分两步进行：
ve[j]和vl[j]可以采用下面的递推公式计算： （1）向汇点递推 ve(源点) = 0 ； ve(j) = Max{ ve(i) + dut(<i, j>)}
p
Vi
Vj
公式意义：从指向顶点Vj的弧的活动中取最晚完成的一 个活动的完成时间作为Vj的最早发生时间ve[j]
L[i] 0 2 3 6 6 8 7 7 10 16 14
L[i]-e[i] 0 2 3 0 2 3 0 0 3 0 0
总结：
有向无环图是描述一项工程或系统的进行过 程的有效工具。 AOV网（顶点表示活动的有向网）与拓扑排序 －－解决工程或系统能否顺利进行；
AOE网（边表示活动的有向网）和关键路径问 题－－估算整个工程完成所必须的最短时间，求 解哪些活动为关键活动。
总之，关键路径的求解操作包括： 1）计算 ve[j] 和 vl[j]
① 向汇点递推
ve(源点) = 0 ； ve(j) = Max { ve(i)+ dut(<i, j>)} ② 向源点递推 vl(汇点) = ve(汇点);
vl(i) = Min { vl(j) – dut(<i, j>)} 2）判断 l(i) = e(i)的活动（关键活动）
如上所述，计算顶点的ve值是在拓扑排序的过
程中进行的，需对拓扑排序的算法作如下修改：
1）在拓扑排序之前设初值，令ve(i)=0（0<=i<n-1）;
2）在算法中增加一个计算vi的直接后继vj的最早发生 时间的操作：若 ve(i)+dut(<i,j>) > ve(j), 则 ve(j) = ve(i)+dut(<i,j>)； 3）为了能按逆拓扑有序序列的顺序计算各顶点的vl值， 需记下在拓扑排序的过程中求得的拓扑有序序列，则需要 在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则 在计算求得各顶点的 ve 值之后，从栈顶至栈底便为逆拓 扑有序序列。
环，不能求关键路径，算法终止；否则执行步骤（3）。
3）从汇点vn出发，令vl[n-1]= ve[n-1]，按逆拓扑有序求 其余各顶点的最迟发生时间vl[i] (n-2 ≥i≥ 0)； 4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s) 和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)， 则为关键活动。
1
v2 v1 v3
v5
v4
a6=3 v6
练习：求下图AOE网的关键路径
事件 j 1 2 3 4 5 6 7 8 9
e v[j] 0 6 4 5 7 7 16 14 18
Lv[j] 0 6 6 8 7 10 16 14 18
活动 i 1 2 3 4 5 6 7 8 9 10 11
e[i] 0 0 0 6 4 5 7 7 7 16 14
汇 点
由于整个工程只有一个开始点和一个完成点，在正 常的情况（无环）下，网中只有一个入度为零的点（称 作源点）和一个出度为零的点（称作汇点）
依据AOE-网可以研究什么问题？
（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？
完成工程的最短时间是从源点到汇点的最长路径的
长度。路径长度最长的路径叫做关键路径。
求关键路径的算法
Status CriticalPath (ALGraph G){ //G为有向网，输出G的各项关键活动 if(!TopologicalOrder(G，T)) return ERROR； vl[0..G.vexnum-1]=ve[G.vexnum-1]； //初始化顶点事件的最迟发生时间 while(!StackEmpty(T)) //按拓扑逆序求各顶点的vl值 for(Pop(T,j)，p=G.vertices[j].firstarc；p；p=p->nextarc){ k=p->adjvex； dut=*(p—>info)； //dut<j，k> if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut； } //for for(j=0；j<G.vexnum；++j) //求ee，el和关键活动 for(p=G.vertices[j]；p；p=p->nextarc){ k=p->adjvex； dut=*(p—>info)； ee=ve[j]；el=vl[k]-dut；tag = (ee==e1) ? ‘*’:’’； printf(j，k，dut，ee，el，tag)； //输出关键活动 } } //CriticalPath
活动的最迟开始时间l(i)，这是在不推迟整个工程完 成的前提下，活动ai最迟必须开始进行的时间。
a6的最早开始时间是5，最迟开始时间是8。如a6推迟3天开 始或延迟3天完成，都不会影响整个工程的完成。 l(i)－e(i)两者之差意味着完成活动ai的时间余量。 我们把l(i)＝e(i)的活动叫做关键活动。 显然，关键路径上的所有活动都是关键活动，因此提 前完成非关键活动并不能加快工程的进度。
v5表示a4和a5已经完 成， a7和a8可以开始
与每个活动相联系的数是 执行该活动所需的时间
v9 表 示 整 个 工 程 的 结 束
上图AOE-网中：
共有11项活动：a1,a2,a3,…a11；
共有9个事件：v1,v2,v3,…v9，每个事件表示在它之 前的活动已经完成，在它之后的活动可以开始。
源 点
e(s)＝ ve(i) l(s)＝ vl(j) - dut(<i，j>)
顶点
ve
vl
活动
e
l
l-e
v1 v2 v3 v4 v5 v6
0 3 2 6 6 8
0 4 2 6 7 8
a1 a2 a3 a4 a5 a6 a7
a8
0 0 3 3 2 2 6
6
1 0 4 4 2 5 6
7
1 0 1 1 0 3 0
例：求下图AOE网的关键路径
v2
v1
v5
v4 v3
a6=3 v6
拓扑序列：V1、V3、V2、V5、V4、V6 ve(源点) = 0 ； ve(j) = Max{ ve(i) + dut(<i, j>)}
vl(汇点) = ve(汇点); vl(i) = Min { vl(j) – dut(<i, j>)}
第7章
7.1 图的定义和术语
7.2 图的存储结构
图
7.3 图的遍历
7.4 图的连通性问题
7.5 有向无环图及其应用
7.6 最短路径
7.6 最短路径
所谓最短路径问题是指：如果从图中某一顶 点（称为源点）出发到达另一顶点（称为终点）
的路径可能不止一条，如何找到一条路径使得沿
此路径上各边的权值总和达到最小。

重复上述，直到S中包含V中其余各顶点的最短路径。
（2） 向源点递推 由上一步的递推，最后总可求出汇点的最早发生时 间ve[n]。因汇点就是结束点，最迟发生时间与最早发生
时间相同，即vl[n]=ve[n]。从汇点最迟发生现时间vl[n]
开始，利用下面公式：
Vi Vj
S
vl(汇点) = ve(汇点);
vl(i) = Min{ vl(j) – dut(<i, j>) }

定义了S集合和D数组并对其初始化后，迪杰斯特拉算法 在进行中，都是从S之外的顶点集合中选出一个顶点w， 使D[w]的值最小。于是从源点到达w只通过S中的顶点， 把 w 加入集合S中，并调整D中记录的从源点到集合中
每个顶点v的距离：
取D[v]和D[w]+cost[w][v]中值较小的作为新的D[v]
从v1到v9的最长路径是（v1,v2,v5,v8,v9），路径长 度是18。
事件vi的最早发生时间
V9 的 最 早 发 生 时 间 是 18
假设开始点是v1，从v1到vi的最长路径长度叫做事 件vi的最早发生时间。这个时间决定了所有以vi为尾的 弧所表示的活动的最早开始时间。 用e(i)表示活动ai的最早开始时间。
V4
20
10
V0
V1 V2 V3 V4 V5
10
50 60 ∞ 30 100 60 90
V3 V2
50
如何在计算机中 求得最短路径？
ຫໍສະໝຸດ Baidu
Dijkstra提出了一个按路径“长度”递增的
次序，逐步得到由给定源点到图的其余各点间的
最短路径的算法：

假设我们以邻接矩阵cost表示所研究的有向网。
迪杰斯特拉算法需要一个顶点集合，初始时集合内 只有一个源点V0 ，以后陆续将已求得最短路径的顶
求最早发生时间ve的算法
Status TopologicalOrder(ALGraph G，Stack &T){ //有向网G采用邻接表，求各顶点事件最早发生时间ve(全局变量) //T为拓扑序列顶点栈，s为零入度顶点栈。 FindInDegree(G，indegree)；//对各顶点求入度 InitStack(S)； //建零入度顶点栈S for(i=0；i<G.vexnum； ++i) if(!indegree[i])Push(S，i) //入度为0者进栈 count=0； InitStack(T)； ve[0..G.vexnum-1]=0； //初始化 while(!StackEmpty(S)){ Pop(S，j)； Push(T，j)；++count; for(p=G.vertices[j].firstarc；p；p=p->nextarc){ k=p—>adjvex； //对i号顶点的每个邻接点的入度减l if(--indegree[k]==0)Push(S，k)；//若入度减为0，入栈 if(ve[j]+*(p->info)>ve[k] ) ve[k]=ve[j]+*(p->info)； } //for *(p->info)=dut(<j,k>) } //while if(count<G.vexnum) return ERROR； //该有向网有回路 else return OK；} //TopologicalOrder
点加入到集合中，到全部顶点都进入集合了，过程
就结束了。集合可用一维数组来表示，设此数组为 S，凡在集合S以外的顶点，其相应的数组元素S[i] 为 0 ，否则为 1 。

另需一个一维数组D，每个顶点对应数组的一个单元，
记录从源点到其他各顶点当前的最短路径长度，其初值 为D[i]=cost[V0][i]，i=1…n。数组D中的数据随着算法 的逐步进行要不断地修改