[Fwd: JGraphT contribution : Bellman-Ford algorithm]

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[Fwd: JGraphT contribution : Bellman-Ford algorithm]

John Sichi
Guilluame Boulmi has contributed an implementation of the Bellman-Ford
shortest-path algorithm, so if you've got a directed graph with negative
edge weights, this is your lucky day.  

(Guillaume, I'm guessing your surname from your email address; if it's
incorrect, please let me know.  Also, do you have a sourceforge account,
and do you want CVS write access to jgrapht?)

I committed Guillaume's code into CVS after adding support for generics
and making a few changes to make it more similar to the existing
DijkstraShortestPath class.  However, the two still have some interface
differences, so next I will take a look at Guillaume's enhanced Dijkstra
code and see if it can be integrated.

I also added some unit tests.  I removed some French comments because
javac was complaining about them in UTF8, and my translation attempts
would have been worse than no comments at all :)


-------- Forwarded Message --------

> From: gu boulmi <[hidden email]>
> To: [hidden email]
> Subject: JGraphT contribution : Bellman-Ford algorithm
> Date: Thu, 5 Jan 2006 11:42:10 +0100 (CET)
>   Hi and happy new year,
>   Please find attached the Bellman-Ford algorithm I
> have written using JGraphT objects. It could close the
> feature request 846561 I think.
>   I have also written a new class for Dijkstra
> algorithm with dedicated DijkstraIterator.
>   The iterator was designed such that it that could be
> subclassed in case the seen-vertex-container change or
> in case path-cost-computation changed (e.g. with
> vertex weights taken into account) or in case not all
> outgoing-edges should be looped over (we could decide
> some edges should not be part of the returned paths).
>   Furthermore paths are not represented as edge-lists
> but as a linked-list of path-element, similar to the
> sub-optimality property of shortest paths.
>   Although I have not used Java generics, I hope it
> could be included in the next release 0.7.
>   Best regards,
>   Guillaume
> ___________________________________________________________________________
> Nouveau : téléphonez moins cher avec Yahoo! Messenger. Appelez le monde entier à partir de 0,012 €/minute !
> Téléchargez sur http://fr.messenger.yahoo.com