Re: [jgrapht-users] Question on JGraphT

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

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