- Forum
- General C++ Programming
- Finding the longest path in a graph
Finding the longest path in a graph
I was asked to find the longest path in a graph. I was thinking about using Dijsktra's algorithm after multiplying all the weights with -1 and run the program in normal way and find the shortest path. And then I'll multiply with -1 again and get the longest path. I think this should give me the longest path, do you think it would work? And also, I'm dealing with considerably big data, such as 1.000.000 nodes and many more edges. etc. and I have a time limit of 2 seconds and memory limit of 128mb. Can you suggest any other data structure instead of Adjacency Matrix? Because I'm pretty sure it will exceed the limits. Any help would be much appreciated.
go from A to B ad nauseam, then jump to C. So lets assume that you can't repeat an edge.
Your modified Dijkstra would not work, analyze the supposition on which the algorithm is based.
iirc, the longest path is NP, ¿are you sure that you understood the problem correctly?
Your modified Dijkstra would not work, analyze the supposition on which the algorithm is based.
iirc, the longest path is NP, ¿are you sure that you understood the problem correctly?
Last edited on
Topic archived. No new replies allowed.