[SciPy-User] Efficient Dijkstra on a large grid

Zachary Pincus zachary.pincus@yale....
Wed Apr 10 11:54:20 CDT 2013


Hi all,

In the image scikit (skimage) we also have a very efficient cython implementation of Dijkstra's algorithm for pathfinding through *dense* n-d grids.
http://scikit-image.org/docs/dev/api/skimage.graph.html

The specific utility of this code is that it operates on raw numpy arrays (as opposed to sparse arrays as in the scikit-learn and scipy implementations). The algorithm uses the values in the array as weights for pathfinding from a given start point either to one or more end-points, or to every point in the array. Valid moves through the grid can be given as a set of offsets, so you could, say, simulate different chess-peice moves. 

There is a second class that is savvy about image geometry, so "travel costs" are weighted to account for the fact that axial moves in a grid are shorter than diagonal moves. In this way, the travel costs from a given point through a uniform array will look more like circles than axis-oriented diamonds, which is what you get with a naive algorithm.

It's built on an extremely fast heap implementation by Almar Klein, so the algorithm runs in essentially real-time for point-to-point finding for 1024x1280 image arrays. (I use it in interactive image-segmentation tools.)

As such, I think this would probably be a useful codebase for your monster pathfinding -- especially the dense grid part.

Zach



On Apr 10, 2013, at 10:02 AM, Lars Buitinck wrote:

>> Date: Wed, 10 Apr 2013 07:24:16 +0200
>> From: Gael Varoquaux <gael.varoquaux@normalesup.org>
>> Subject: Re: [SciPy-User] Efficient Dijkstra on a large grid
>> To: SciPy Users List <scipy-user@scipy.org>
>> Message-ID: <20130410052416.GB8796@phare.normalesup.org>
>> 
>> In scikit-learn, we have a Dijkstra implemented in cython, using
>> Fibonacci heaps:
>> 
>> https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/graph_shortest_path.pyx
> 
> Dijkstra's is in SciPy as well:
> https://github.com/scipy/scipy/blob/master/scipy/sparse/csgraph/_shortest_path.pyx#L32
> 
> -- 
> Lars Buitinck
> Scientific programmer, ILPS
> University of Amsterdam
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user



More information about the SciPy-User mailing list