Re: [Boost-users] Shortest path feasibility code

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.

Paul

On Tue, Nov 18, 2008 at 8:01 PM, Scott McMurray <me22.ca+boost_at_[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."
> ~ http://www.rosenlaw.com/lj16.htm
>
> 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. "
> ~ http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/bellman_ford_shortest.html
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users