0
$\begingroup$

let's say I have an undirected unweighted graph where each edge can be "visited" only once. How can I get the longest path? I've seen something like NP-hard or depth-first search. Thanks for help

$\endgroup$
0
$\begingroup$

If there are no cycles in your graph, you can put -1 weights on each edge and search for the shortest path with the Dijkstra algorithm (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) for example.

If there are cycles, your problem is NP-hard indeed, and you need to proceed differently, with integer programming for example.

Note. The shortest path with negative weights equals the longest path. If weights are unitary, and the shortest path is, say -20, then the longest path has length 20.

$\endgroup$
  • $\begingroup$ But I want longest path $\endgroup$ – Flash Nov 17 '15 at 14:02
  • $\begingroup$ Yes, but a shortest path with negative weights will give you the longest path! $\endgroup$ – Kuifje Nov 17 '15 at 14:46
  • $\begingroup$ Can you tell me why is that so? :-)) Because I'm quite new in graphs and I know Dijkstra algorithm just a little $\endgroup$ – Flash Nov 17 '15 at 15:59
  • $\begingroup$ More explanation can be found in en.wikipedia.org/wiki/… . Note that it's just about acyclic graphs. In general your problem is NP-hard $\endgroup$ – Omid Ebrahimi Nov 19 '15 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.