The longest path in a Directed Acyclic Graph (DAG) is a path that has the maximu
ID: 3691863 • Letter: T
Question
The longest path in a Directed Acyclic Graph (DAG) is a path that has the maximum length. Given a DAG with unweighted edges, the length of a path is the number of edges in the path. Write an algorithm that finds the longest path in such a DAG. Given a DAG with weighted edges and the weights of edges are real numbers, the length of a path is the sum of weights of the edges in the path. Write an algorithm that finds the longest path in such a DAG. Now consider a scheduling problem for a project which consists of n jobs. Each job i has an execution time t_i, and a precondition that specifies jobs i can not be started before some jobs are finished. The precondition relations between jobs are acyclic. Multiple jobs can be executed at the same time if the preconditions for those jobs are satisfied. Give an algorithm to find a schedule that minimized the total time to finish all jobs.Explanation / Answer
Longest Path in a Directed Acyclic Graph with weighted edges
The longest path problem doesn’t have optimal substructure property. In fact, the Longest Path problem is NP-Hard for a general graph. However, the longest path problem has a linear time solution for directed acyclic graphs. The idea is similar to linear time solution for shortest path in a directed acyclic graph, we use Tological Sorting.
Initialize distances to all vertices as minus infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph. Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
Longest Path in a Directed Acyclic Graph with unweighted edges
This problem is NP-complete. What this means in practice is that for a large random graph there's no known algorithm that can solve this in reasonable time.
If the graph has a special property, like being small, or being acyclic, or alternatively if you just wish to find a long path and not necessarily the longest, then that might be doable.
longest-path (G)
Input: Unweighted DAG G = (V,E)
Output: Largest path cost in G
Topologically sort G
For each vertex v Vin linearized order
Do dist(v) = max(u,v)E{dist(u) + 1}
Return maxvV{dist(v)
}
Algorithm to find a schedule that minimizes the total time to finish all the jobs
A schedule gives the anticipated start times of each job resource, while a sequence gives only the order in which the jobs are to be done.
The total time to complete all the jobs does not depend on the ordering. This is called shortest process time sequence rule.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.