Find the longest path in a directed cyclic graph from a source s to a destination f. Assume no positive weight cycles exists

Question

Hi,

i have to Find the longest path in a directed cyclic graph from a source s to a destination f. Assume no positive weight cycles exists even though no positive weight cycles exist, cycles of 0 or negative weights do exist. Can someone suggest an algorithm for finding the longest path in this case. please cite source if possible.

thanks

Answer 1

If you got a DCG, you can just loop forever before you get to your target, that would be the "longest path". In that case, the question is incomplete, and the algorithm probably looks different depending on the specifics.

This sounds like homework.

Answer 2

I am not sure if this will work (need to check it) but... you can do something similar to:

Let min = min weight on the graph.
max = max weight on the graph.
Set new weights for all edges = wNew(e) = max - (wOld(e)-min).

now there are now negative wights and the weights are in reverse order (meaning if w(e1) was bigger than w(e2) it is now smaller).

What if we will search now for the shortest path?

Answer 3

Just negate your edge weights and run a shortest path algorithm (e.g., Bellman-Ford).

Zero-weight cycles could be an issue. You'll need to break ties on your paths by picking the shortest one (in length, not in weight). One way to do that is to make your weights be a pair (-(original weight), 1), add them pairwise, and do lexicographic ordering.

See also http://stackoverflow.com/questions/1256331/longest-path-betwean-two-vertices