We can find the longest path in a graph by applying 2 bfs.
1st BFS is from our start node. The node which appear in last will be the
one farthest from the start node.Let this node be end1.
Now again apply bfs from end1 and the last node which appears will be the
another end.
Here I have made
This not a bad thought experiment, but sorry this isn't true. First,
there is a problem of cycles. If a graph is undirected, you can pick
any edge and go back and forth an arbitrary number of times along that
edge to make any path as long as you want.
So if there exists _any_ path there is no
// 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)
{
//
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
Nice. The code is very clean.
It's worth noting in case anyone is intending to implement this that
it's easy find graphs where exhaustive DFS runs in exponential time.
One that's easy to envision is a chain of diamonds
S8o8o8o ... o8D where S is the source and D the destination
with all edges
Thank You very much friends.
I ve read algorithm Topological Sorting.
First we have to perform the topological sorting ( in Linear Time ) on
the graph.
Then we can find which is the Longest Path in that ordering.
But it works for only DAG ( Directed Acyclic Graphs ).
I ve done it. But after
Beware of cycles.
Don
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
In case cycle is present in the graph then we cant have a longest path in
the graph.Therefore the problem reduces to the longest path in a
tree.(Assuming the graph is connected).
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Wed, Feb 22, 2012 at 11:23
First verify that the graph doesnt have the cycles using BELLMAN-FORD
ALGORITHM. then apply DFS.. this will certainly give you a right answer...
On Thu, Feb 23, 2012 at 10:01 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh :Even if you are considering its as a graph with no cycles , you
