Critical Paths - The solution
(Page 3 of 4 )
It is important to note that here we have no circles in the graph. Considering this, we can apply with a little modification the algorithm we used to calculate the shortest road inside a graph with no circle inside it. Yes, you are right; it is the topological order-based technique.
Here it is a graph drawn so that you can see and understand this better:
-->Image Courtesy of Kátai Zoltán- Introduction to Graphs<--
Practically, we are going to invert the topological order shortest-path algorithm and query for the longest road. You remember that the topological sort allowed us to order the vertexes in a way that all of the edges were directed from the left to the right.
This way we could just follow with the edges in this order, to perform an approximation with each edge. We start from the root vertex of course. If we follow this principle, by the time we arrive at a vertex, we've already performed approximations through all of its incoming edges, and now we will have the shortest road from the root to this vertex.
This is possible because the shortest path's sub-road is also the shortest road. So now, we will invert the statement, and instead of searching for the minimal distance between the source and the outgoing edges of a vertex, we will search for the maximum distance. From this, we will find out the longest road from the drain.
We invert the graph, calculate the maximum length, and now we will get the longest roads from the source. For all the distances for which we did not yet calculate the maximum distance, we will have inside this two arrays minus one. The arrays are named intuitively the Longest Road Drain (lr_drain) and the Longest Road Source (lr_source).
Our function will return as a result the maximum road value and generate the roads through the maximum leads within some additional arrays. There will be one for the normal call and one for the inverse graph call.
In the case of both calls we will find out the same maximum road length; what differs is only the shortest roads between the stations of the critical path. Also, from the first call, we will find out the longest road path as well. The second call on the inverse is only required to find out the earliest time possible to start a job.
The algorithm itself is a combination of the depth search algorithm and the topological order-based technique to find out the shortest (now the longest) road inside a graph. Instead of first building the topological order and later using it, we will make the approximation as soon as we get the node, so we do not need to store it.
Furthermore, we save any preliminary results in the longsetroad array, so we will call the recursion only if, for that vertex, we have received approximation yet. This will mean that, in that index, the array is minus one. This way we will approximate with each edge at most once, and ensure that we can save the vertex, through we polished our maximum road a little in the nextCritNode array. All of this will become clearer as soon as you read the next page.
Next: The code snippet >>
More Code Examples Articles
More By Gabor Bernat
