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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-01-08 02:50:58

Ramprasad Natrajan wrote:

>>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. 

Ah... I see there's explicit check for non-negative edge weidht. And adding
a constant to all weight can change relative length of paths, so is not an
option.

I would though that for DAGs, negative edge weights are not a problem. Wait
a minute -- there's a special function for DAGs. I was able to get decent
results with it -- I attach a modified version of min_max_paths.cpp

>>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.

Seems like min_max_paths.cpp is very broken. It attempts to find max
distance path in a graph with cycles! 

- Volodya