// 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 <kknarenkris...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.