RE: [boost] Re: Boost Graph Library: Longest path using Dijkstra's

From: Ramprasad Natrajan (ramkaka_at_[hidden])
Date: 2004-01-06 23:46:46

>Vladimir Prus  wrote:
>
>From graph theory standpoint, for DAG the longest path can be found by
>inverting all edge weights and then finding the shortest path.
>

There are two ways we can invert 1) invert the sign 2) invert the magnitude. 
Dijkstra doesn't accept negative edge weights. If I invert magnitudes, the 
relaxing part will break. (1/50 + 1/50) != (1/70 + 1/30). So I had to cahnge 
the comparison function.

>As for 'dijkstra_shortest_paths' parameters, I'm not 100% sure. However, it
>seems that using '0' for initinity parameter and MAXINIT for 'zero' is a
>mistake. You only want to invert the comparison.
>
>And... looking at examples/min_max_paths.cpp, I see that there's code to
>find longest path which in fact passes different comparison, but leaves
>infinity/zero the same. I suggest that you look at the file.

When I tried running the min_max example, my program 'aborted' at the 
dijikstra function call. And this was without me changing anything from the 
example. I was having the same problem on my program until I swapped the 0 
and infinity. I am using gcc version 3.3.2, boost 1.30.2 under fedora.

Thanks for your help,

Ram

_________________________________________________________________
Start getting interview calls immediately. 
http://go.msnserver.com/IN/40245.asp Post your CV on naukri.com today.