Longest path!


The problem taken form acm uva site , Longest Path

Since we need to know the longest path for a source node given, the graph of cities to be traversed in DFS. The Depth First Traversal visits all nodes reachable from the source node. Here is the function needed for DFS in this problem.

void dfs(long snode)
{
long i;
if(sum>max)
{
max=sum;
p=snode;
}
for(i=0;i<num;i++)
{
if(n[snode][i]==1&&visited[snode][i]==0&&i!=start)
{
visited[snode][i]=1;
sum++;
dfs(i);
sum--;
visited[snode][i]=0;
}
}
}

dfs.png

Advertisements
  1. #1 by Sheila Eka on December 25, 2010 - 3:56 am

    I like your post on ur blog.

    I read some articles, they said that application of longest path is traveling salesman problem (TPS). I still work on it for my thesis, but i have a problem when I’m trying to make a program used Java.

    Do you have a pseudocode / full program of longest path? I really need it for helping me finishing my thesis…

    thx before

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: