Administrator

Olivier Lefevre wrote:
> Hi, > > What is the algorithm used for Kshortest 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 

In reply to this post by John Sichi

In reply to this post by John Sichi

Administrator

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 BellmanFord 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 BellmanFord (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 /<[hidden email]>/* a écrit : > > De: John V. Sichi <[hidden email]> > Objet: Re: Question on JGraphT > À: [hidden email] > Cc: [hidden email], [hidden email] > Date: Mercredi 4 Mars 2009, 1h09 > > Olivier Lefevre wrote: > > Hi, > > > > What is the algorithm used for Kshortest 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 > > 
I see that this is a fairly old post, but hopefully this will be useful anyway.
I have experimented with this same algorithm, and unfortunately I think it may not always correctly produce the K shortest paths. Consider a graph with the following edges (posted as .dot file for graphviz), where we are searching for the 3shortest paths from S to U: graph G { autosize=false; size="20,12!"; rankdir=LR; S  U [label="1"]; S  a1 [label="1"]; a1  a2 [label="1"]; a2  a3 [label="1"]; a3  a4 [label="1"]; a4  V [label="1"]; S  b1 [label="3"]; b1  b2 [label="1"]; b2  b3 [label="1"]; b3  b4 [label="1"]; b4  b5 [label="1"]; b5  U [label="1"]; S  c1 [label="2"]; c1  b2 [label="1"]; V  U [label="1"]; V  d1 [label="1"]; d1  U [label="1"]; V  e1 [label="1"]; e1  e2 [label="1"]; e2  U [label="1"]; } The path (S, a1, a2, a3, a4, V, U) should be one of the 3shortest paths from S to U. However, after four iterations, the three shortest paths stored for V will be {(S, U, V), (S, U, d1, V), (S, U, e2, e1, V)}. This will prevent the path {(S, a1, a2, a3, a4, V)} from being stored for V at the fifth iteration, which will prevent it from being passed on to U at the sixth iteration. The problem comes from the fact that we only store simple paths for each vertex at each iteration. If we allow paths to have loops, then we can prove correctness for the algorithm using essentially the same method that is used to prove correctness for BellmanFord. SRS 
Hi, In a mood of making a cleanup of my unused email addresses, I came across your email. It might be useful that I answer you before I give up for good to visit my Yahoo mailbox :) I will not answer exactly to your question (you may consider to attach a JUnit test case for the members willing to look at the bug you mentioned), on the hand I want to clarify the poor performance of the algorithm to warn new JGraphT users. Initially I designed the algorithm (a long time ago...) mainly for the purpose of complete graphs with possibly negative weight cycles. However, as the name of the class 'KShortestPaths' does not refer to this specific property (of possible negative cycles), it might be misleading for the majority of users whose graphs are only with nonnegative edge weights. Indeed, what is 100% true is that it is far far too slow compared to other algorithms for nonnegative edge weights :( Unfortunately everybody seems to perform the 'KShortestPaths' algorithm with nonnegative edge weights... In order not to mislead users, it might be worth to rename the class or to remove the class completely (I will feel hurt) and replace it with a bestinclass algorithm. You may think of the REA algorithm (Recursive Enumeration Algorithm) by Jimenez and Marzal (see http://www.springerlink.com/content/pl0054nt2d0d2u3t/ ) or to the Yen's algorithm (as already pointed by somebody at http://stackoverflow.com/questions/12773525/kshortestalternativepathalgorithmjavaimplementations ). I definitely submitted to JGraphT a not satisfying implementation for the 'KShortestPaths' class. Sorry for that. Le Mercredi 29 juillet 2015 14h05, SSovine <[hidden email]> a écrit : I see that this is a fairly old post, but hopefully this will be useful anyway. I have experimented with this same algorithm, and unfortunately I think it may not always correctly produce the K shortest paths. Consider a graph with the following edges (posted as .dot file for graphviz), where we are searching for the 3shortest paths from S to U: graph G { autosize=false; size="20,12!"; rankdir=LR; S  U [label="1"]; S  a1 [label="1"]; a1  a2 [label="1"]; a2  a3 [label="1"]; a3  a4 [label="1"]; a4  V [label="1"]; S  b1 [label="3"]; b1  b2 [label="1"]; b2  b3 [label="1"]; b3  b4 [label="1"]; b4  b5 [label="1"]; b5  U [label="1"]; S  c1 [label="2"]; c1  b2 [label="1"]; V  U [label="1"]; V  d1 [label="1"]; d1  U [label="1"]; V  e1 [label="1"]; e1  e2 [label="1"]; e2  U [label="1"]; } The path (S, a1, a2, a3, a4, V, U) should be one of the 3shortest paths from S to U. However, after four iterations, the three shortest paths stored for V will be {(S, U, V), (S, U, d1, V), (S, U, e2, e1, V)}. This will prevent the path {(S, a1, a2, a3, a4, V)} from being stored for V at the fifth iteration, which will prevent it from being passed on to U at the sixth iteration. The problem comes from the fact that we only store simple paths for each vertex at each iteration. If we allow paths to have loops, then we can prove correctness for the algorithm using essentially the same method that is used to prove correctness for BellmanFord. SRS  View this message in context: http://jgraphtusers.107614.n3.nabble.com/ReQuestiononJGraphTtp107942p4025031.html Sent from the jgraphtusers mailing list archive at Nabble.com.  _______________________________________________ jgraphtusers mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgraphtusers  Go from Idea to Many App Stores Faster with Intel(R) XDK Give your users amazing mobile app experiences with Intel(R) XDK. Use one codebase in this allinone HTML5 development environment. Design, debug & build mobile apps & 2D/3D highimpact games for multiple OSs. http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140 _______________________________________________ jgraphtusers mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
Free forum by Nabble  Edit this page 