Re: [Boost-users] Shortest path feasibility code

Subject: Re: [Boost-users] Shortest path feasibility code
From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2008-11-18 23:01:09

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