[SciPy-Dev] Dijkstra distances with limit

[Eric Larson]

Hello,

I'm doing some calculations of Dijkstra distances on a large surface
(>100,000 nodes) between a certain subset of nodes of interest (~10,000).
Moreover, I'm only interested in finding pairs of points that are within a
certain (relatively small) distance of one another.

The current `sparse.csgraph.dijkstra` implementation allows me to get the
distances between all 10,000 points of interest, which is helpful. However,
this is many orders of magnitude slower than it would be if I limited the
search to just those distances within my small limit of interest (which is
a couple orders of magnitude smaller than the longest distance). While the
package `networkx` has this feature using the argument `cutoff`, it is not
written in C and suffers performance-wise compared to the Cython
implementation in Scipy.

It seems like it would be fairly straightforward to modify `dijkstra` and
the Cython code (`_dijkstra_directed` and `_dijkstra_undirected`) in
`_shortest_path.pyx` to take an argument like `max_dist` that limits how
large a distance may be used. I'd be happy to do this, assuming this is an
acceptable new feature. Thoughts?

Cheers,
Eric
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20131011/259d5557/attachment.html>