Boost logo

Boost :

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,


Start getting interview calls immediately. Post your CV on today.

Boost list run by bdawes at, gregod at, cpdaniel at, john at