# Longest path in a cyclic, directed and weighted graph

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?

• "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. :) – Raphael May 26 '16 at 19:34