#path #graph #order #root-path #increasing #length #short

short-paths

Iterate over s-t paths in a graph in increasing order of length

1 unstable release

Uses old Rust 2015

0.1.0 Feb 4, 2018

#6 in #increasing

MIT license

33KB
769 lines

short-paths

This is an implementation of the algorithm to find short s-t paths in a graph given by Eppstein in this paper. Specifically, it constructs the path graph as described in section 2, then does a Dijkstra-esque walk from the root of the path graph to generate paths in increasing order of length.

Because we use a basic implementation of Dijkstra's algorithm to generate the shortest path tree, the preprocessing step is O(m log n). Furthermore, since we are not using any of the sophisticated heap selection algorithms and we are returning paths as full lists of edges rather than implicitly, the time to generate the i'th path is O(log i + e) where e is the number of edges in that path.

Dependencies

~650KB
~15K SLoC