For certain projects, it is possible to represent the different steps using a weighted and directed graph. With a graph, it is possible to see the different paths available, all starting from the same point of origin and going to the same endpoint. Some of these paths can be parallel, which means that the steps that make up the path can take place at the same time. Among all these paths, the one with the highest weight is the critical path. The weight here represents the minimum time required to complete the entire project.
Steps for resolving a problem using the critical path method:
-
Represent the situation using a weighted and directed graph, taking into account all the prerequisite steps.
-
Determine the weight of each path that connects the starting and ending vertices.
-
The critical path of the graph is the path with the highest weight. Simply interpret the answer according to the situation.
Creating a graduation album
A high school graduation committee is preparing a graduation album. The school principal asks them to estimate the time required to produce the album. The following table shows the steps required to create the graduation album.
|
Tasks |
Time (days) |
Prerequisites |
|
A: Buy the film |
1 |
None |
|
B: Charge cameras |
1 |
A |
|
C: Take pictures of the student council |
3 |
B |
|
D: Take pictures of teachers |
2 |
B |
|
E: Take pictures of sports teams |
1 |
B |
|
F: Have the pictures processed |
2 |
C-D-E |
|
G: Prepare the layout |
5 |
F |
|
H: Have the album signed by the album committee |
3 |
G |
|
I: Have the album signed by the principal |
2 |
G |
|
J: Print the albums |
5 |
H-I |
Determine the minimum number of days required to create the graduation album.
Solution
Step 1
Step 2
Start - A - B - C - F - G - H - J - End = 20
Start - A - B - C - F - G - I - J - End = 19
Start - A - B - D - F - G - H - J - End = 19
Start - A - B - D - F - G - I - J - End = 18
Start - A - B - E - F - F - H - J - End = 18
Start - A - B - E - F - G - I - J - End = 17
Step 3
In this example, the critical path is Start - A - B - C - F - G - H - J - End since its weight is the highest, that is, 20 days. Therefore, the album will take at least 20 days to create.