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
|
