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 <dondod...@gmail.com> 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 <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*- 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 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.
