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

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?

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 stackoverflow.com/questions/1256331/long....

Thanks for your answer. I was just wondering if we have to negate only the negative edge weights or all edge weights irrespective of the sign of the weight. – user465983 Oct 7 '10 at 15:04 You have to negate all the weights.

– Keith Randall Oct 7 '10 at 22:44.

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.

Pls read question properly. It says NO POSITIVE WGHT , THEN HOW CAN YOu assume that looping forever will give longest path. – user465983 Oct 5 '10 at 17:01.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.