Critical path principle

One   The finishing touch

AOV  The net can reflect the sequential constraints between activities , But in practical engineering , Sometimes there is more than a sequence of activities , And the duration , How long must it take to complete this activity . At this time, another network is needed ——AOE network , That is, the active net is represented by an edge .AOE A net is a weighted directed acyclic graph , Nodes represent events , Arcs represent activities , The weight on the arc represents the duration of the activity .

for example , There is a 6  Time 、8 An active project , As shown in the figure below .V0 and V5 Represent the beginning and end of the project respectively , In activity  a0、a2  After the end , Time  V1  Before you can start , stay  V1  After the end , Activities  a3、a4  Before you can start .

In practical engineering applications, two problems usually need to be solved .

1  It is estimated that at least how long it will take to complete the whole project .

2  Determine which activities are critical , That is, if the activity is delayed , It will affect the progress of the whole project .

stay  AOE  In the net , The path with the largest length of the weighted path from the source point to the sink point is the critical path . Activities on the critical path are critical activities .

Two   Four core concepts

To determine the critical path, we should clarify four concepts ： The earliest time of the incident 、 At the latest , And the earliest time of the activity 、 At the latest .

1  event  Vi The earliest occurrence time of  ve[i]

Explore the frontier , seek （ Arctail  Ve +  Edge weight ） The maximum of

2  event  Vi The latest time of occurrence of  vl[i]

Investigate the edge , seek （ Arc head Vl -  Edge weight ） The minimum value of

3  Activities  ai=<Vj,Vk>  The earliest occurrence time of  e[i]

The earliest occurrence time of the arc tail .

4  Activities  ai=<Vj,Vk>  The earliest occurrence time of l[i]

The latest occurrence time of the arc head minus the boundary value .

3、 ... and   The illustration

Here is a  AOE  network , Find its critical path .

1  Find topological sorting sequence , Keep it in  topo[]  Array .

2  Sort the sequence according to topology （0,2,1,3,4,5）, Solve the earliest occurrence time of each node from front to back  ve[]

ve[0]=0

v2[2]=ve[0]+15=15

ve[1]=max{ve[2]+4,ve[0]+2}=19

ve[3]=ve[1]+10=29

ve[4]=max{ve[2]+ve[1]+19}=38

ve[5]=max{ve[4]+5,ve[3]+6}=43

3  In reverse topological order （5,4,3,1,2,0）, Solve the latest occurrence time of each node from back to front  vl[]. The latest occurrence time of the initialization sink is the earliest occurrence time of the sink , namely  vl[n-1]=ve[n-1]. Examine the edges of other nodes , Arc head  vl -  The minimum value of the edge weight .

vl[5]=ve[5]=43

vl[4]=vl[5]-5=38

vl[3]=vl[5]-6=37

vl[1]=min{vl[4]-19,vl[3]-10}=19

vl[2]=min(vl[4]-11,vl[1]-4)=15

vl[0]=min{vl[2]-15,vl[1]-2}=0

After calculation , The earliest and latest occurrence time of the event are shown in the table below .

event	ve[i]	vl[i]
0	0	0
1	19	19
2	15	15
3	29	37
4	38	38
5	43	43

4  Calculate the earliest and latest occurrence time of each activity .

• Activities a0=<V0,V1>：e[0]=ve[0]=0;l[0]=vl[1]-2=17

• Activities a1=<V0,V2>：e[1]=ve[0]=0;l[1]=vl[2]-15=0

• Activities a2=<V2,V1>：e[2]=ve[2]=15;l[2]=vl[1]-4=15

• Activities a3=<V1,V3>：e[3]=ve[1]=19;l[3]=vl[3]-10=27

• Activities a4=<V1,V4>：e[4]=ve[1]=19;l[4]=vl[4]-19=19

• Activities a5=<V2,V4>：e[5]=ve[2]=15;l[5]=vl[4]-11=27

• Activities a6=<V3,V5>：e[6]=ve[3]=29;l[6]=vl[5]-6=37

• Activities a7=<V4,V5>：e[7]=ve[4]=38;l[7]=vl[5]-5=38

If the earliest occurrence time of the activity is equal to the latest occurrence time , Then this activity is a key activity

Activities	e[i]	l[i]	Key activities
a0	0	17
a1	0	0	yes
a2	15	15	yes
a3	19	27
a4	19	19	yes
a5	15	27
a6	28	37
a7	38	38	yes

5  A critical path consisting of key activities from the source to the sink  V0-V2-V1-V4-V5

Four   Algorithm steps

1  Using topological sorting algorithm , Save the topology sorting results in  topo[] Array .

2  Initialize the earliest occurrence time of each time 0, namely  v[i]=0,i=0,1,2...n-1

3  Calculate the earliest occurrence time of each event from front to back according to the topological order , Loop through these operations ：a  Take out the nodes in the topology sequence  k;b  With a pointer  p  Point to in turn  k  Every adjacent point of , Get the sequence number of the adjacency point  j=p.v, Update node  j  The earliest occurrence time of  ve[j]

if(ve[j]<ve[k]+p.weight)  ve[j]=ve[k]+p.weight

4  The latest occurrence time of each time  vl[i]  Are initialized to the earliest occurrence time of the sink , namely  vl[i]=ve[n-1]

5  The latest occurrence time of each event is calculated from the back to the front according to the reverse topological order , Loop through these operations ：a  Take out the sequence number in the inverse topological sequence  k;b  With a pointer  p  Point to in turn  k  Every adjacent point of , Get adjacency point serial number  j=p.v, Update node  k  The latest time of occurrence of  vl[k]

if(vl[k]>vl[j]-p.weight) vl[k]=vl[j]-p.weight

6  Determine whether the activity is a key activity . Ruiyu every node i, They all use pointers p Point to in turn  i  Every adjacent point of , Get the sequence number of the adjacency point  j=p.v, Computing activities <Vi,Vj> The earliest and latest occurrence time of , As shown in the figure below , If  e  and  l  equal , Then activity <Vi,Vj> For key activities .