[algogeeks] Re: Longest Path in A Graph

// 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*

-- 
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.