Loading...

algogeeks@googlegroups.com
[Prev] Thread [Next]  [Prev] Date [Next]
[algogeeks] Re: Longest Path in A Graph Don Fri Feb 24 08:01:10 2012
// 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 depthfirst 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*  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.
 [algogeeks] Longest Path in A Graph krishna kishore 2012/02/22
 Re: [algogeeks] Longest Path in A Graph Dheeraj Sharma 2012/02/22
 [algogeeks] Re: Longest Path in A Graph Don 2012/02/22
 Re: [algogeeks] Re: Longest Path in A Graph saurabh singh 2012/02/22
 Re: [algogeeks] Re: Longest Path in A Graph atul anand 2012/02/22
 Re: [algogeeks] Re: Longest Path in A Graph mitaksh gupta 2012/02/22
 [algogeeks] Re: Longest Path in A Graph Krishna Kishore 2012/02/23
 [algogeeks] Re: Longest Path in A Graph Don 2012/02/24 <=
 [algogeeks] Re: Longest Path in A Graph Don 2012/02/24
 [algogeeks] Re: Longest Path in A Graph Gene 2012/02/24
 Re: [algogeeks] Re: Longest Path in A Graph Mad Coder 2012/02/29
 [algogeeks] Re: Longest Path in A Graph Gene 2012/02/29