How do find the longest path in a cyclic Graph between two nodes?

Posted by Nazgulled on Stack Overflow See other posts from Stack Overflow or by Nazgulled
Published on 2010-04-20T22:15:46Z Indexed on 2010/04/20 22:23 UTC
Read the original article Hit count: 405

Filed under:

graph

|

longest-path

|

c

|

cyclic

Hi,

I already solved most the questions posted here, all but the longest path one. I've read the Wikipedia article about longest paths and it seems any easy problem if the graph was acyclic, which mine is not.

How do I solve the problem then? Brute force, by checking all possible paths? How do I even begin to do that?

I know it's going to take A LOT on a Graph with ~18000. But I just want to develop it anyway, cause it's required for the project and I'll just test it and show it to the instructor on a smaller scale graph where the execution time is just a second or two.

At least I did all tasks required and I have a running proof of concept that it works but there's no better way on cyclic graphs. But I don't have clue where to start checking all these paths...

© Stack Overflow or respective owner

Related posts about graph

C++: Error in Xcode; "Graph::Coordinate::Coordinate()", referenced from: ...

as seen on Stack Overflow - Search for 'Stack Overflow'
In a program I am writing, I wrote for two classes (Coordinate, and Graph), with one of them taking the other as constructor arguments. When I try to compile it I get the following error for Graph.cpp: Undefined symbols: "Graph::Coordinate::Coordinate(double)", referenced from: Graph::Graph()… >>> More
How to create Line Graph and Bar graph on same parameters in asp.net

as seen on C# Corner - Search for 'C# Corner'
We can use GDI+ to draw chart components in C# or VB.NET language in memory and once the components are drawn in memory, we can save the drawing in an image on the Web server. Once the image is saved, we can display this image in an ASP.NET page using any Image tag or image control. >>> More
Display Graph using Boost Graph Library

as seen on Stack Overflow - Search for 'Stack Overflow'
Can anyone please tell me that once I've created a graph using Boost Graph library, how can I display that graph? My biggest concern is that the edge weights are coming from an exernal data source over the network. And I need to be able to display the edgeweights live as they get updated. >>> More
Matlab multiple graph types inside one graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have a task to draw electrostatic field between two electrodes( at given sizes and shape ), what i have now is that i draw the electrodes with area plot (area(elect_x,elect_y)) the graph looks like this: ------------------.--- |.. .---. |.. |...| |… >>> More
[C++] Write connected components of a graph using Boost Graph

as seen on Stack Overflow - Search for 'Stack Overflow'
I have an file that is a long list of weighted edges, in the following form node1_id node2_id weight node1_id node3_id weight and so on. So one weighted edge per line. I want to load this file into boost graph and find the connected components in the graph. Each of these connected components… >>> More

Related posts about longest-path

Graph longest path

as seen on Stack Overflow - Search for 'Stack Overflow'
How can we find a longest path in a graph ?? I thought we can use depth first but I couldn't find any easier implemantation for it ? >>> More
print the longest path between two leaf nodes

as seen on Stack Overflow - Search for 'Stack Overflow'
hi all, we know how to computer diameter but i came across a question where they asked you to print this longest path .. how can it be done? >>> More
Longest Path in Boost Graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, Sorry if this is a very basic questions for some of you but I'm new to C++ (let alone Boost Graph Library) and couldn't figure out this problem. So far I've been able to formulate/gather code to create a graph using the code below. Now I'm trying to figure out the code to find the longest… >>> More
3 page longest path on a website

as seen on Stack Overflow - Search for 'Stack Overflow'
i have a log file which maintains source entry for each page.all the pages share the common file. source means from what page did user arrive on the target page. I want to find the most common 3 page path for all the pages on the website. Example log file: source Target 1 2 1 3 2… >>> More
Creating a program to find longest path

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi everyone, I'm fairly new to programming and I'm having a few problems. Basically I have to make a function that will find the lengths of all the paths through a network diagram. I've been working on this for hours but I can't seem to get anywhere. Using recursion I can navigate through every path… >>> More