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

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


ANSWERS:


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 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 now search for the shortest path?


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 Longest Path between two vertices


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.



 MORE:


 ? Starting Services -- Directed Acyclic Graph
 ? How can I find the shortest cycle in a Directed, Weighted Graph?
 ? Finding path of zero/Negative weight between Two Nodes on Graph by Utilizing Negative Cycles
 ? How to refer to custom Vertexes to add an Edge, using JGraphT
 ? Java and JGraphT - Do not understand result - Pass by value/reference issue or something else?
 ? Java and JGraphT - Do not understand result - Pass by value/reference issue or something else?
 ? Java and JGraphT - Do not understand result - Pass by value/reference issue or something else?
 ? I don't understand this pass by value and pass by reference concept in java
 ? Java pass by reference issue
 ? Java Pass by value understanding