CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphs
David
David

Reputation: 7486

Relation between Critical Path and the Longest Path

The Critical Path is the essence of solving the parallel precedence-constrained scheduling problem.

The problem: Given a set of jobs of specified duration to be completed, with precedence constraints that specify that certain jobs have to be completed before certain other jobs are begun, how can we schedule the jobs on identical processors (as many as needed) such that they are all completed in the minimum amount of time while still respecting the constraints?

I'm having a tough time understanding the connection between this and the longest path through the graph, which is apparently the solution. I would assume that the answer would be the shortest time because we want the minimum amount of time. Why is this related to the longest path, not the shortest path?

Upvotes: 2

Views: 1408

Answers (3)

kostas
kostas

Reputation: 41

The longest path algorithm focuses on longest cumulative durations, and ensures that all dependencies are respected.

But the shortest path algorithm, while it is efficient in finding minimal paths, may inadvertently schedule tasks earlier than their dependencies would allow. So violating the vertex/jobs dependencies.

Here are Wikipedia references:

  • Longest_path_problem

  • Critical_path_method "A critical path is determined by identifying the longest stretch of dependent activities and measuring the time required to complete them from start to finish"

Here is an example that shows how the shortest path algorithm can violate the vertex dependencies (or job dependencies)

Suppose we have a DAG with three vertices/jobs A,B and C. Also the topological order A B C.

Task A_start,A_end 3 days, Task B_start,B_end 2 days and task C_start,C_end 1 day durations accordingly.

Suppose these Dependencies:

Task B can't start before A_ends. Task C can't start before A_ends. Task C can't start before B_ends.

The dependencies have zero weight.

Here is the DAG: enter image description here

When the shortest path algorithm run will do the following:

  1. Initialise the A_start->A_end distance = 0.
  2. Processing Nodes in topological order:
  • A_start->A_end distance=3,
  • A_end->B_start distance=3,
  • B_start->Bend distance=5,
  • A_end->C_start distance=3 (Here the alternative B_end->C_start distance=5 is skipped, choosing the shortest path.)
  • C_start->C_end distance =4,

B_end and C_end going to Project_End from B_end distance=5 from C_end distance=4 so Project_End earliest completion 5 days.

So the shortest path algorithm ignored the dependency of B_end->C_start which is 5 and instead moved from A_end to C_start with time 3. Also the expected duration for the project is 6 days instead of 5.

In contrast the longest path algorithm ensures that all the dependencies are respected.

  1. Initialise the A_start->A_end distance = 0.
  2. Processing Nodes in topological order:
  • A_start->A_end distance = max(3, prev distance)
  • A_end->B_start distance = max(3, prev distance)
  • B_start->Bend distance = max(5, prev distance)
  • A_end->C_start distance = max(3, prev distance)
  • B_end->C_start distance = max(5, 3)=5
  • C_start->C_end distance = 6

B_end and C_end going to Project_End from B_end distance=5 from C_end distance=6 so Project_End earliest completion 6 days. So in the longest path the dependencies are respected and the C_start starts after B_end.

Upvotes: 0

Paul Draper
Paul Draper

Reputation: 83421

  1. Create a vertex representing the end state.
  2. Create one vertex for every task.
  3. For each task T
    1. For each task T2 that depends on T (and for the end state)
      1. Create a directed edge E from T's vertex to T2's vertex
      2. Set weight of the E to the time required for T.

Then, the critical path is the longest path through the graph. Think about this for a bit, and convince this is true.

This train of thought helps me:

The critical path must start with a task with no dependencies and end at the final state. No task can be completed until all of its dependencies are met.

If task A must be done before B, and B must be done before C, then time from task A to task C is at least A->B + B->C.

If C has another dependency B' which has a dependency A, then the time from A to C is at least A->B' + B'->C.

Thus, the longest path from A to C is what matters.

The shortest path would solve the problem if some dependency of a task had to be met. The longest path solves the problem when all dependencies have to be met.

Upvotes: 0

mcdowella
mcdowella

Reputation: 19621

The length of the shortest schedule is related to the longest path because there is nothing you can do, no matter how many processors you have, to get the job done faster than the longest path. No job on the longest path can start before the previous job is finished, so you have to do them one after the other.

If you never run out of processors, you can always start a job as soon as all the jobs it depends on have finished, so each job gets finished as soon as the longest path to its end point finishes, and the whole job finishes when you have completed the longest path.

Upvotes: 1

Related Questions