From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-01-05 02:12:42
Ramprasad Natrajan wrote:
> 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, &d, weightmap, indexmap,
> std::greater<int>(), closed_plus<int>(),
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk