Thread: Re: [jgrapht-users] Question on JGraphT
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
jgrapht-users
|
From: John V. S. <js...@gm...> - 2009-03-04 00:09:47
|
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 |
|
From: gu b. <bou...@ya...> - 2009-03-09 13:30:06
|
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
|
|
From: gu b. <bou...@ya...> - 2009-03-09 12:59:50
|
Hi,
I'm Implmentation
--- 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
|
|
From: gu b. <bou...@ya...> - 2009-03-09 13:22:49
|
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 Bellman-Ford 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 Bellman-Ford 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 <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
|
|
From: John V. S. <js...@gm...> - 2009-03-09 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 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 > > |
|
From: SSovine <so...@gm...> - 2015-07-29 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 3-shortest 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 3-shortest 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 Bellman-Ford.
SRS
--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-Question-on-JGraphT-tp107942p4025031.html
Sent from the jgrapht-users mailing list archive at Nabble.com.
|
|
From: gu b. <bou...@ya...> - 2015-12-04 21:36:51
|
Hi,In a mood of making a clean-up of my unused email addresses, I came across your e-mail.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 non-negative edge weights. Indeed, what is 100% true is that it is far far too slow compared to other algorithms for non-negative edge weights :(Unfortunately everybody seems to perform the 'KShortestPaths' algorithm with non-negative 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 best-in-class 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/k-shortest-alternative-path-algorithm-java-implementations ). I definitely submitted to JGraphT a not satisfying implementation for the 'KShortestPaths' class. Sorry for that. Le Mercredi 29 juillet 2015 14h05, SSovine <so...@gm...> 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 3-shortest 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 3-shortest 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 Bellman-Ford. SRS -- View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-Question-on-JGraphT-tp107942p4025031.html Sent from the jgrapht-users mailing list archive at Nabble.com. ------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list jgr...@li... https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X