Nice. The code is very clean. It's worth noting in case anyone is intending to implement this that it's easy find graphs where exhaustive DFS runs in exponential time. One that's easy to envision is a chain of "diamonds" S<8>o<8>o<8>o ... o<8>D where S is the source and D the destination with all edges directed left-to-right so that it is acyclic. For N diamonds, there are 2^N paths to check. So you would have to know a lot about the structure and/or size of the graph before you could put this algorithm in a real program.
Since this problem is NP-hard, there's near zero hope of doing better than exhaustive DFS on general graphs. On the other hand, if the graph is directed and acyclic, there is a simple linear time algorithm as was noted by one of the posters. On Feb 24, 11:08 pm, Don <[email protected]> wrote: > It was pointed out to me by Dave, a very sharp frequent contributor to > this group, that a different definition of a cycle will produce > different results in some cases. If a cycle is defined as following > the same edge in the same direction more than once, rejecting cycles > of that type will often produce longer paths. > > To use this rule, replace the "else" portion of my code with > > { > // Try all valid adjacent nodes > for(j = 0; j < n; ++j) > if (edges[from][j]) > { > edges[from][j] = false; > longestPath(j,to,depth+1); > edges[from][j] = true; > } > } > > Don > > On Feb 24, 9:42 am, Don <[email protected]> wrote: > > > > > // Assuming that the graph with n nodes is specified by an adjacency > > matrix edges[n][n] > > // where edges[i][j] is true if an edge exists from i to j > > > // Implements depth-first search with restriction that each > > // node may only be visited once. > > int longestPath(int from, int to, int depth=0) > > { > > // Length of longest path encountered > > static int max; > > > // Start new search > > if (depth == 0) max = 0; > > > // Save path followed > > path[depth] = from; > > > // Detect arrival at destination > > if (from == to) > > { > > if (depth > max) // Is this the longest path so far? > > { > > savePath(); // Copy the current path > > max = depth; > > } > > } > > else > > { > > // Avoid cycles > > visited[from] = true; > > > // Try all valid adjacent nodes > > for(j = 0; j < n; ++j) > > if (edges[from][j] && !visited[j]) > > longestPath(j,to,depth+1); > > > // This node is available to visit again > > visited[from] = false; > > } > > > // Return length of longest path found > > return max; > > > } > > > On Feb 22, 6:05 am, krishna kishore <[email protected]> wrote: > > > > Hi Gentle Men, Can any Please let me know How to Find a LONGEST PATH in a > > > Graph ( directed or Undirected but unweighted ). > > > INPUT: we have to give the Source vertex and Destination Vertex. > > > OUTPUT: it should include the LENGTH OF PATH and PATH as well. > > > Remember the graph should not be weighted. > > > > Any suggestions are accepted for sure. > > > And Thanks in Advance. > > > -- > > > > *Vignesh*- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
