Critical Path Algorithm Cont.
How To: Critical Path Algorithm (version 2)
- Apply the backflow algorithm to the digraph.
- Create the priority list by listing the tasks in order from longest critical time to shortest critical time.
This version of the Critical Path Algorithm will usually be the easier to implement.
Applying this to our digraph from the earlier example, we start applying the backflow algorithm.
Solution
We add an end vertex and give it a critical time of [latex]0[/latex].
We then move back to [latex]T_4,T_9,[/latex] and [latex]T_{10}[/latex], labeling them with their critical times.
From each vertex marked with a critical time, we go back. [latex]T_7[/latex], for example, will get labeled with a critical time [latex]11[/latex] – the task time of [latex]4[/latex] plus the critical time of [latex]7[/latex] for [latex]T_{10}[/latex]. For [latex]T_5[/latex], there are two paths to the end. We use the longer, labeling [latex]T_5[/latex] with critical time [latex]5+7=12[/latex].
Continue the process until all vertices are labeled. Notice that the critical time for [latex]T_5[/latex] ended got replaced later with the even longer path through [latex]T_8[/latex].
We can now quickly create the critical path priority list by listing the tasks in decreasing order of critical time:
Priority list: [latex]T_2,T_6,T_1,T_3,T_5,T_7,T_8,T_{10},T_4,T_9[/latex]
Applying this priority list using the list processing algorithm, we get the schedule:

In this particular case, we were able to achieve the minimum possible completion time with this schedule, suggesting that this schedule is optimal. This is certainly not always the case.
In most cases the critical path algorithm will lead to a very good schedule. There are cases where it will not. Unfortunately, there is no known algorithm to always produce the optimal schedule.