Winter Vacation Training Day 4 (01.30)

Area 4.1 : Critical Path Algorithm

Example :

Figure 10.1 : Critical Path Algorithm

Critical Path Algorithm is an algorithm solving Critical Path based on Topological Sort.

The Topological Sequence T (here is [A, B, C, D, E, F, G, H, I]) is the core of the algorithm.

To solve the problem, we need solve etv(Earliest Time of Vertex), ltv(Latest ~).

Step 1, find the first node in T(here is A), etv[A]=0

Table 10.1-a : Critical Path Algorithm(a)

Next, find after nodes (here is B and C). etv[B]=etv[A]+(A, B), etv[C]=etv[A]+(A, C).

Table 10.1-b : Critical Path Algorithm(b)

Do as that again.

Table 10.1-c : Critical Path Algorithm(c)

Next one is G. But there are 2 edges : (D, G) and (E, G). Which one is answer?

In fact, for a node v and edges (U, v), etv[v]=max({etv[U]+(U, v)} (I)

Proof of statement I

If we use the smaller time, it will be irregular.
For example, there are A, B, C and edges (A, C)=1, (B, C)=2, etv[A]=etv[B]=0
The etv of a node is the earliest time of the node.
If etv[A]=0, because (A, C)=1, it means that C should begin after time 1.
As above, etv[B]=0, because (B, C)=2, it means that C should begin after time 2.
So, C should begin after time max(1,2)=2.

So, etv[G]=max(5.71+2.94, 5.54+2.75)=8.65

Solving etv[H] is easier. etv[H]=8.33.

Table 10.1-d : Critical Path Algorithm(d)

The last one is I. There are also 2 edges (G, I), (H, I). So etv[I]=max(8.65+2.87, 8.33+3.35)=11.68

Table 10.1-e : Critical Path Algorithm(e)

But, what about ltv?

We need another sequence T’, inverse topological sequence. Solving it is also easy, doing a topological sort from I in the inverse graph is OK.

The sequence T’ (here is [I, H, G, F, E, D, C, B, A]) is also very important.

Step 1, let ltv[I]=etv[I]=11.68

Table 10.1-f : Critical Path Algorithm(f)

Then, find after nodes (here is G, H). ltv[G]=ltv[I]-(G, I), ltv[H]=ltv[I]-(H, I) :

Table 10.1-g : Critical Path Algorithm(g)

Do as that again :

Table 10.1-h : Critical Path Algorithm(h)

Next one is B. Again, there are two edges (B, D), (B, E). Which one is the answer now.

In fact, for a node u and edges (u, V), ltv[u]=min({ltv[V]-(u, V)}). (II)

Proof of statement II

It is the inverse of statement I.
If we use the bigger time, it will delay the period of the work.
For example, there are A,B,C and edges (A, B)=3, (A, C)=2, ltv[B]=ltv[C]=5.
As above, the ltv of a node is the latest time of a node.
If ltv[B]=5, because (A, B)=3, so A should begin before time 2.
As above, ltv[C]=5, because (A, C)=2, so A should begin before time 3.
So, A should begin before time 2.

So, ltv[B]=min(5.87-2.77, 6.06-2.6)=3.1.

Solving ltv[C] is also easier. ltv[C]=3.41.

Table 10.1-i : Critical Path Algorithm(i)

The last one is A. We know, ltv[A]=min(ltv[B]-(A,B), ltv[C]-(A,C))=0.

Table 10.1-j : Critical Path Algorithm(j)

Now, we get all etv and ltv. We can comput ete(Earliest Time of Edge) and lte(Latest ~).

Here, ete[(u, v)]=etv[u], lte[(u, v)]=ltv[v]-(u, v).

edge	ete[]	lte[]
(A, B)	0	0.16
(B, D)	2.94	3.1
(D, G)	5.71	5.87
(G, I)	8.65	8.81
(B, E)	2.94	3.46
(E, G)	5.54	6.06
(A, C)	0	0
(C, F)	3.41	3.41
(F, H)	5.95	5.95
(H, I)	8.33	8.33

Table 10.1-k : Critical Path Algorithm(k)

Now, we comput lte-ete for each edge :

edge	delta
(A, B)	0.16
(B, D)	0.16
(D, G)	0.16
(G, I)	0.16
(B, E)	0.52
(E, G)	0.52
(A, C)	0
(C, F)	0
(F, H)	0
(H, I)	0

Table 10.1-l : Critical Path Algorithm(l)

We notice that the value delta of some edges are 0.

Now we label them in the graph.

Figure 10.2 : Critical Path

These edges build a path. This is the Critical Path.

And, this is all of Cirtical Path Algorithm.

Given Score :
    Difficulty : 2
x   Basic Score : 196
Score : 1291