View Question
 Question
 Subject: Java Code question Category: Computers > Programming Asked by: tokes-ga List Price: \$30.00 Posted: 01 Dec 2004 17:44 PST Expires: 31 Dec 2004 17:44 PST Question ID: 436873
 ```I am trying to write code that will compute the longest path in a directed acyclic graph. I am trying to keep the time complexity to not exceed O(n^2), with 'n' being the number of vertices in the graph. I think recursion is the best way to approach this type of problem but i am having trouble with this approach. What would the code be? Must be in java.```
 ```Hi tokes-ga, There are two keys to the solution. The first is, as you suggest, recursion. The second is memoization, where we'll save computed answers so we don't have to compute them again in the future. Memoization is a programming trick that trades space (memory needed by the program) for time (computation effort). This allows us to achieve the O(n^2) time bound that you desire. To grasp the recursion, observe that the longest path starting from any particular vertex, v, is the maximum longest path starting from a neighboring vertex v', plus the single step from v to v'. Turning to the Java code, assume you have a Vertex class that represents a single vertex in the graph. An array of each vertex's neighbors is retrieved with the Vertex class's method: public Vertex[] getNeighbors() We'll put our code within a Graph class that contains a private variable that is an array of Vertex objects. I imagine that you have already written these classes with similar methods, along with code for initializing them. Then we can write the following code: public class Graph { import java.util.*; private Vertex[] vertices; // your constructor and initialization code goes here. it will // initialize the vertices array. // the public method that looks for the longest path starting // from each vertex in the graph public LinkedList findLongestPath() { LinkedList longestPath = null; Hashtable memo = new Hashtable(); for (int i = 0; i < vertices.length; i++) { LinkedList tmpPath = findLongestPathFromVertex(vertices[i], memo); if ((longestPath = null) || (tmpPath.size() > longestPath.size())) { longestPath = tmpPath; } } return longestPath; } // a recursive function to find the longest path from a // particular vertex in the graph. private LinkedList findLongestPathFromVertex(Vertex v, Hashtable memo) { // we might have already computed the answer LinkedList longestPath = (LinkedList) memo.get(v); // if we didn't, we'll compute it now if (longestPath == null) { LinkedList longestNeighborPath = null; Vertex[] neighbors = v.getneighbors(); for (int i = 0; i < neighbors.length; i++) { // this is the recursive step LinkedList tmpPath = findLongestPathFromVertex(neighbors[i], memo); // we only want to keep the maximum longest neighbor path if ((longestNeighborPath == null) || (tmpPath.size() > longestNeighborPath.size())) { longestNeighborPath = tmpPath; } } if (longestNeighborPath != null) { longestPath = longestNeighborPath.clone(); } else { // this covers the case for when there are no neighbors longestPath = new LinkedList(); } // here we add the current vertex to the longest path at a neighbor longestPath.addFirst(v); // and we record the result, which is the second key, memoization memo.put(v, longestPath); } return longestPath; } } I hope this answers your question. Sincerely, dogbite-ga Google Answers Researcher```