Re: [jgrapht-users] Question on JGraphT

[SSovine <so...@gm...>]

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.