Shortest path feasibility code
Hi, Is there any public domain code that implements shortest path feasibility or negative cycle detection? Thanks, Paul
On Mon, Nov 17, 2008 at 23:44, paul <paul.delamusica@gmail.com> 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.ht...
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@gmail.com> wrote:
On Mon, Nov 17, 2008 at 23:44, paul <paul.delamusica@gmail.com> 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.ht... _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (4)
-
Dmitry Bufistov -
paul -
Paul De La Musica
-
Scott McMurray