[SciPy-Dev] Dijkstra distances with limit

[Jacob Vanderplas]

Hi Eric,
I think that this would be a very useful enhancement.  I was curious about
how Dijkstra's algorithm could be modified to allow this: I searched around
and it seems to be fairly straightforward (see, e.g.
http://rmandvikar.blogspot.hu/2008/07/dijkstras-algorithm.html).  I'll look
out for your pull request!
   Jake

On Fri, Oct 11, 2013 at 10:06 AM, Eric Larson <larson.eric.d at gmail.com>wrote:

> 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
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20131012/45a5663e/attachment.html>