Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: gu boulmi <boulmigu@ya...>  20090309 12:59:50
Attachments:
Message as HTML

Hi, I'm Implmentation  En date de : Mer 4.3.09, John V. Sichi <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... 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 
From: John V. Sichi <jsichi@gm...>  20090304 00:09:47

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 
From: gu boulmi <boulmigu@ya...>  20090309 13:30:06
Attachments:
Message as HTML

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 <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... 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 
From: gu boulmi <boulmigu@ya...>  20090309 12:59:50
Attachments:
Message as HTML

Hi, I'm Implmentation  En date de : Mer 4.3.09, John V. Sichi <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... 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 
From: gu boulmi <boulmigu@ya...>  20090309 13:22:49
Attachments:
Message as HTML

Hi, I have not implemented this algorithm based on a reference paper, 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 KShortestPathsIterator#next and BellmanFordIterator#next). Complexity "m*n" is because it's a variant of BellmanFord and the "k" factor is because the method RankingPathElementList#addPathElements is O(k). If you find  En date de : Mer 4.3.09, John V. Sichi <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... 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 
From: John V. Sichi <jsichi@gm...>  20090309 22:44:12

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 /<jsichi@...>/* a écrit : > > De: John V. Sichi <jsichi@...> > Objet: Re: Question on JGraphT > À: lefevrol@... > Cc: jgraphtusers@..., boulmigu@... > 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 > > 
From: SSovine <sovine5@gm...>  20150729 12:04:57

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. 
From: gu boulmi <boulmigu@ya...>  20151204 21:36:51
Attachments:
Message as HTML

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 <sovine5@...> 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 jgraphtusers@... https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
Sign up for the SourceForge newsletter:
No, thanks