Boost logo

Boost :

From: Ramprasad Natrajan (ramkaka_at_[hidden])
Date: 2004-01-08 05:36:57


Thanks a lot. The dag shortest path worked.

Ram

>From: Vladimir Prus <ghost_at_[hidden]>
>Reply-To: Boost mailing list <boost_at_[hidden]>
>To: boost_at_[hidden]
>Subject: [boost] RE: Re: Boost Graph Library: Longest path using Dijkstra's
>Date: Thu, 08 Jan 2004 10:50:58 +0300
>
>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
>
><< min_max_paths.cpp >>
>_______________________________________________
>Unsubscribe & other changes:
>http://lists.boost.org/mailman/listinfo.cgi/boost

_________________________________________________________________
Free drafts to 700 locations.
http://server1.msn.co.in/msnleads/suvidha/dec03.asp?type=hottag Click here.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk