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