
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 3: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 3:49 PM

If it's a DAG, it seems fairly easy to compute on top of the DFS.



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 7:31 PM

You can get the critical path by modifying the relaxation function of a DAG shortest path algorithm.


Coordinator
May 13, 2007 at 7:31 PM

This discussion has been copied to a work item. Click here to
go to the work item and continue the discussion.

