Tip:
Highlight text to annotate it
X
(male narrator) So we wanna find the priority list
for this diagraph using the critical path algorithm,
and there's a couple of versions of the critical path algorithm.
We're gonna start with sort of the...
sort of definitional version
that turns out not to be very efficient,
uh...but we're gonna...
it'll help us understand how this works.
So the critical path, you might remember,
is the longest sequence of tasks in the diagraph.
So if we look at this,
we can see that this sequence here...
is the longest sequence of tasks in the diagraph.
Uh...this-this series of tasks, which by the arrows tells us
these have to be completed in order,
has a total time of, let's see here, 10, 15, 25, 28.
And so this is the longest path in the diagraph.
And so the theory here is that, gee, wouldn't it be nice
to get Task 2 done first?
And so it's gonna become
the first task on our priority list.
So now we're gonna imagine what would happen
if Task 2 wasn't part of the...the graph at all?
So it was already sort of used up.
What's the longest path now?
And it turns out this remaining path
is still the longest,
and so the next task on our list is gonna be Task 6.
But once we remove that...vertex
and its corresponding edges, now...
if we ask what is the longest path,
it turns out both of these have the same length.
This one has length...
let's see here, 6 and 5's 11, uh...11, 14, 21.
And-and this path here is the same.
And since they're the same,
we'll go ahead and use the task with the smaller number first,
and so we'll go ahead and say,
Task 1 is now the head of this...critical path.
Now once we've added Task 1, though,
then we remove Task 1 from our list,
and our critical path now shifts down here,
which means Task 3
will be the next task on our priority list.
So now we imagine we remove that,
and we say, what's my new longest path?
Well, my new longest path is now here--5, 3, 7,
which is longer than 4, 3, 7.
And so Task 5 becomes next on my...critical path list.
We remove that from our...graph,
uh...along with its edges.
And we say, okay, what's the longest now?
And you can probably see that this is gonna be longest now,
and so Task 7 gets added next.
If I remove this and say, what's my longest path now?
It's gonna be here-- task...uh...8 and then Task 10.
Uh...right, 3 and 7 gives us our longest path now,
so I'll go ahead and add Task 8.
And now once we remove that,
all of our order requirements are done,
and we're just left with these three sort of individual tasks,
uh...the longest of which is Task 10.
The next longest is Task 4.
And the only task left is Task 9.
And so this is our critical path...based...
critical path algorithm-based priority list.