[jgrapht-developers] [Fwd: JGraphT contribution : Bellman-Ford algorithm]

[John V. S. <js...@gm...>]

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 :)

JVS

-------- Forwarded Message --------
> From: gu boulmi <bou...@ya...>
> To: js...@gm...
> 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