Boost logo

Boost :

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.


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