2
$\begingroup$

I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights.

In my research so far I have found out that you need to generate -G from graph G and then run a shortest path algorithm on it to find the longest path in G. Of course this won't work if -G contains negative cycles. But that's excatly what I need to do. Consider following graph (which I created quickly in paint..):

enter image description here

The red letters are just there for identification. The red numbers are the value of the vertex and the blue numbers are the edge weights. The edge weights are generated with the following formula:

$$ Weight = \frac{destination}{source} $$

I am looking for the longest path from A to F - but the longest simple path. That means that a vertex must not be visited more than once. By simply looking at it I can see that it is A - B - E - F. But if I tried to generate -G and then run the Bellman-Ford algorithm on it it would fail because there would be negative cycles like B - E - D - B.

I am aware that it is not possible if you look for paths in which a vertex can be visited more than once. But if you look for simple paths only, is it still not possible?

$\endgroup$
  • 1
    $\begingroup$ "there is no X" is not the same as "it is impossible to find X" is not the same as "there is no algorithm that can always find X" is not the same as "I'm not able to find X" is not the same as "I am not able to find an algorithm that always find X". Gotta be precise. :) $\endgroup$ – Raphael May 26 '16 at 19:34
3
$\begingroup$

Longest Path is NP-hard; the reduction from Hamiltonian Path is almost trivial.

That means that we do not know any algorithm with even polynomial running-time. You have to compromise.

Of course, the problem is easier for special classes of graphs, for instance both undirected and directed acyclic graphs.

$\endgroup$

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.