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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-01-05 02:12:42

Ramprasad Natrajan wrote:

> Hey,
> 
> I am new to the boost graph libraries. I was trying to find the longest
> path in a DAG using the dijkstra's algorithm. I used the following syntax:
> 
> dijkstra_shortest_paths(hcg, s, &p[0], &d[0], weightmap, indexmap,
>                           std::greater<int>(), closed_plus<int>(),
>                           0,MAXINT,dijkstra_visitor<null_visitor>());
> 
> where MAXINT is defined to be larger than the largest sum of distances but
> much less than max numeric limit. But, this doesn't seem to do the trick.
> Anyone have any suggestions?

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

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.

HTH,
Volodya