[Solved]: Longest path in a cyclic, directed and weighted graph

Problem Detail: 

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..):

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?

Asked By : Bobface

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57894

3.2K people like this

 Download Related Notes/Documents