南邮数据结构上课关键路径

数据结构DATASTRUCTURE9.5关键路径第九章图

9.1图的基本概念9.2图的存储结构9.3图的遍历9.4拓扑排序99.5与关键路径9.6最小代价生成树9.7最短路径内容提要：

从本节开始讨论图数据结构的应用，包括关键路径、最小代价生成树和最短路径。9.5关键路径9.5.1AOE网络

上一节的AOV网络，用顶点表示活动，有向边表示先决条件，有向图可以表示活动之间的领先关系。第九章图

9.1图的基本概念9.2图的存储结构9.3图的遍历9.4拓扑排序99.5与关键路径9.6最小代价生成树9.7最短路径AOE(边活动网络)：有向图G中，若用顶点代表事件，有向边表示活动，有向边上的权值表示一项活动持续的时间，则称图G为AOE网络。顶点所代表的事件，表示它的入边的活动均已完成，出边的活动可以开始。

AOE网络主要用于估算一项工程的完成时间。AOE网络举例031258467AOE网的例子sfa0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=8a8=4a9=2a10=4ijak=w(i,j)边(i,j)的权值w(i,j)v0(s):整个工程的起点。v8(f):整个工程的终点(结束)。v4:表示活动a3和a4已经完成，a6和a7可以开始。a5:表示活动a5持续的时间是2(天)。整个工程只有一个开始点，AOE就只有一个入度为0的顶点(源点)整个工程只有一个完成点，AOE就只有一个出度为0的顶点(汇点)9.5.2关键路径与关键活动

与AOV网络不同，AOE网络研究以下两个方面：

(1)整个工程至少需要多少时间；

(2)哪些活动是影响工程进度的关键。关键路径法(CMP)就是解决这类问题的方法。

关键路径：从源点到汇点的最长路径。

关键活动：关键路径上的活动。或对整个工程的最短完成时间有影响的活动。即如它不能按期完成就会影响整个工程。031258467sfa0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=8a8=4a9=2a10=4例如:(v0,v1,v4,v7,v8)就是一条关键路径。a0,a3,a7,a10就是关键活动。路径长度=a0+a3+a7+a10=6+1+9+4=19找关键活动的目的：(1)重视关键活动；

(2)缩短整个工期。关键活动对缩短整个工期起着至关重要的作用；非关键活动对缩短整个工期不起作用。因此，对关键活动投入较多的人力和物力，确保工程按期完成，或缩短整个工期。031258467sfa0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=8a8=4a9=2a10=4为了定量找出关键路径，需要以下几个量：(1)事件vi的可能的最早发生时间

earliest(i)=从源点v0到vi的最长路径长度(2)事件vi的允许的最晚发生时间。即在不影响工期的条件下事件vi允许的最晚发生时间。

latest(i)=earliest(n)-从vi到汇点vn的最长路径长度031258467sfa0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=8a8=4a9=2a10=4earliest(4)=a0+a3=6+1=7earliest(5)=a2+a5=5+2=7earliest(8)=a0+a3+a7+a10=6+1+8+4=19Latest(4)=19-(8+4)=7latest(5)=19-(4+4)=11latest(7)=earliest(8)-4=19-4=15earliest(5)=7,latest(5)=11,意义？ak表示的边为<vi,vj>，w(i,j)为ak的权值。(3)活动ak的可能的最早开始时间。

early(k)=事件vi的可能的最早发生时间即early(k)=earliest(i)(4)活动ak的允许的最晚开始时间。

late(k)=latest(j)-w(i,j)(5)若early(k)=late(k),则ak是关键活动。031258467sfa0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=8a8=4a9=2a10=4early(7)=earliest(4)=7late(7)=latest(7)-8=15-8=7early(8)=earliest(5)=7late(8)=latest(7)-4=11因early(7)=late(7),early(8)<>late(8),故a7是关键活动，a8不是关键活动。关键活动必须在它可能的最早开始时间立即开始，否则将影响整个工程。1a3=103258467sfa0=6a1=4a2=5a4=1a5=2a6=9a7=8a8=4a9=2a10=4

项目v0v1v2v3v4v5v6v7v8

earliest(i)064577161519latest(i)0669711171519

项目a0a1a2a3a4a5a6a7a8a9a10

early(k)0006457771615late(k)02466987111715关键路径*

*

*

*9.5.3关键路径算法

(1)计算事件的最早发生时间earliest。从earliest(0)=0开始，自前向后递推计算:earliest(j)=max{earliest(i)+w(i,j)}i

P(j)P(j)是所有以j为头的弧<i,j>的弧尾i的集合。为保证计算earliest(j)时，所有的earliest(i)(i

P(j))已经求得。可以利用拓扑排序。1a3=124a4=1(3)计算活动的最早开始时间early(k)和最晚开始时间late(k)。

early(k)=earliest(i)late(k)=latest(j)-w(i,j)(2)计算事件的最晚发生时间latest。从latest(n)=earliest(n)开始，自后向前递推计算:latest(i)=mim{latest(j)-w(i,j)}j

S(j)S(i)是所有以i为尾的弧<i,j>的弧头j的集合。为保证计算latest(i)时，所有的latest(j)(j

S(i))已经求得。可以利用逆拓扑排序。(4)确定关键路径若early(k)=late(k),则ak是关键活动。467a6=9a7=8关键路径算法的C++描述template<classT>voidLinkedGraph<T>::CriticalPath(){int*early,*late,*earliest,*latst,*t;inti,j,k,top=-1;Enode<T>*p;early=newint[e];late=newint[e];earliest=newint[n];latest=newint[n];t=newint[n];//t用于存放拓扑排序的顶点序列

//此处为(1)，即在拓扑排序中计算earliest[]//此处为(2)，即在逆拓扑排序中计算latest[]//此处为(3)，即计算early[]和late[]

//(4),确定关键路径

for(k=0;k<e;k++)if(early[k]==late[k])cout<<‘a(‘,k,’)’,’isacreticalactivity.’<<endl;

}程序9.14

Earliest函数template<classT>voidExtLGraph<T>::Earliest(int*earliest,int*order){ for(inti=0;i<n;i++)earliest[i]=0;for(i=0;i<n;i++){ intk=order[i]; for(ENode<T>*p=a[k];p;p=p->nextArc) if(earliest[p->adjVex]<earliest[k]+p->w)//计算earliest[k] earliest[p->adjVex]=earliest[k]+p->w; }}程序9.15Latest函数template<classT>voidExtLGraph<T>::Latest(int*latest,int*order,intlongest){ for(inti=0;i<n;i++)latest[i]=longest;for(i=n-2;i>-1;i--){intj=order[i];for(ENode<T>*p=a[j];p;p=p->nextArc) if(latest[j]>latest[p->adjVex]-p->w) latest[j]=latest[p->adjVex]-p->w;}}(3)计算early[]和late[]1a3