Critical Path

Topics: algorithm, graph
May 13, 2007 at 7:03 AM
Is there a way to find a critical path (longest path) using this library?
Also, (this may be a dumb question) once you have a start node and an end node, how do you find the exact path?

Thank you very much for making this library available.
It is extremely useful and I appreciate the effort put into it.

-Nick
Coordinator
May 13, 2007 at 4:44 PM
>> Is there a way to find a critical path (longest path) using this library?
what does graph literature say on this subject?

>> Also, (this may be a dumb question) once you have a start node and an end node, how do you find the exact path?
Could you clarify what you mean by 'exact' path (otherwize your question has a lot of answers).
Coordinator
May 13, 2007 at 4:49 PM
If it's a DAG, it seems fairly easy to compute on top of the DFS.
May 13, 2007 at 7:13 PM
It is a DAG. I build a database schema representation as a graph. Vertexes are tables, edges are foreign key constraints.

I'm really illiterate on graph theory, hence why I'm asking if there is a way to find the critical path using the existing framework or if I have to modify one of the algorithms (DijkstraShortestPathAlgorithm perhaps) to do this. A DAG exactly represents my problem hence why I chose it.

As for the exact path, won't the DFS algorithm give me the shortest path to a node? Assuming, that I have multiple paths to a node, I need the critical path, not the shortest path.

Thank you.

-Nick
Coordinator
May 13, 2007 at 8:31 PM
You can get the critical path by modifying the relaxation function of a DAG shortest path algorithm.
Coordinator
May 13, 2007 at 8:31 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.