Re: [jgrapht-users] Question on JGraphT

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

Thanks Guillaume.  I'll poke around a bit and update the Javadoc with 
what I find.

Olivier, if you are interested in implementing one of the newer 
algorithms, we can incorporate that into the library too.

JVS

gu boulmi wrote:
> 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
> 
>