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.