Boost logo

Boost Users :

Subject: Re: [Boost-users] Shortest path feasibility code
From: Paul De La Musica (paul.delamusica_at_[hidden])
Date: 2008-11-18 23:22:08

OK, what I really need is code that identifies the nodes or edges in
the negative cycle and not just returns true or false.


On Tue, Nov 18, 2008 at 8:01 PM, Scott McMurray <[hidden]> wrote:
> On Mon, Nov 17, 2008 at 23:44, paul <paul.delamusica_at_[hidden]> wrote:
>> Is there any public domain code that implements shortest path feasibility or
>> negative cycle detection?
> "Just as there is nothing in the law that permits a person to dump
> personal property in the public highway, there is nothing that permits
> the dumping of intellectual property into the public domain — except
> as happens in due course when any applicable copyrights expire. Until
> those copyrights expire, there is no mechanism in the law by which an
> owner of software can simply elect to place it in the public domain."
> ~
> As such, unless you can find code written by a government employee in
> the course of their work (which I consider quite unlikely), there is
> not.
> Boost, however, has a very reasonable licence, and Boost.Graph
> provides what you need:
> "The algorithm repeats this loop |V| times after which it is
> guaranteed that the distances to each vertex have been reduced to the
> minimum possible unless there is a negative cycle in the graph. If
> there is a negative cycle, then there will be edges in the graph that
> were not properly minimized. That is, there will be edges (u,v) such
> that w(u,v) + d[u] < d[v]. The algorithm loops over the edges in the
> graph one final time to check if all the edges were minimized,
> returning true if they were and returning false otherwise. "
> ~
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at