k-shortest paths

[Jerry]

Hello everyone,

I am trying to calculate k-shortest paths from one node to another
with an arbitrary cutoff - e.g. 10 shortest paths from node x to node
y. In addition - viable shortest paths would also be subject to a
total distance or time constraint but I could get/calculate that from
the returned paths.

I am using networkx in a pedestrian movement simulation with spatio-
temporal barriers and obstacles so viable shortest paths will change
during the simulation as conditions change. The graph is a
representation of sidewalk and building networks on the University of
Iowa campus. The k-shortest paths would be used to determine
alternate routes if conditions on the shortest path excludes shortest
path edges from traversal. I couldn't find any posts on this and also
couldn't find anything in the documentation. I will look through the
code next but was just wondering if anyone has any information on
something like this.

Thanks,
Jerry

[Aric Hagberg]

We don't have any k-shortest path algorithms yet.
You might take a look at some of the recent algorithmic work in this
area - say
http://citeseer.ist.psu.edu/eppstein94finding.html

We can help you get an algorithm implemented with NetworkX if you identify
a suitable one.

Aric

>
> Thanks,
> Jerry
>