Re: [jgrapht-users] Question on JGraphT

[gu b. <bou...@ya...>]

Hi,
 
I have not implemented this algorithm based on a reference paper. So, it's not Jimenez and Marzal!
Though I'm sure that what I've written is not new and must have been explained previously in many papers.
 
The algorithm is a variant of the Bellman-Ford algorithm but instead of only storing the best path I store the "k" best paths at each pass (se differences between methods KShortestPathsIterator#next and BellmanFordIterator#next).
 
Complexity "m*n" is because it's a variant of Bellman-Ford (whose complexity is O(m*n)) and the "k" factor is because the method RankingPathElementList#addPathElements is O(k) where k is the number of expected paths to be computed (by the way I notice that this "O(k)" piece of information is not in the javadoc documentation).
 
If you find a paper pointing to this kind of algorithm, feel free to update the javadoc documentation.
 
Regards,
 
Guillaume

--- En date de : Mer 4.3.09, John V. Sichi <js...@gm...> a écrit :

De: John V. Sichi <js...@gm...>
Objet: Re: Question on JGraphT
À: lef...@ya...
Cc: jgr...@li..., bou...@ya...
Date: Mercredi 4 Mars 2009, 1h09

Olivier Lefevre wrote:
> Hi,
> 
> What is the algorithm used for K-shortest paths in JGraphT: the REA
algorithm of Jimenez and Marzal?
> 
> Regards,
> 
> Olivier Lefevre
> Freelance bioinformatics developer
> Berlin, Germany

Greetings Olivier,

I don't know the answer, so I'm cc'ing your question to the users
mailing list, as well as Guillaume Boulmier, who developed this code.

Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have
O(K*m*n) for the running time.

JVS