[SciPy-User] useful code: binary heaps and Dijkstra's algorithm/minimum-cost-path for arrays (cython)

Zachary Pincus zachary.pincus@yale....
Tue Dec 1 19:12:44 CST 2009


Hello all,

Thanks to generous contributions from Almar Klein, here are two useful  
bits of code for those interested:

(1) A fast cython implementation, written by Almar, of a binary min  
heap. This of course provides O(log2(N)) pushes to and pops from the  
heap, and O(1) queries of the minimum value. Also, this implementation  
can track an arbitrary integer reference along with each value pushed.  
Further, there is another heap class that keeps an index, so that it  
is possible to query the value for a given reference in O(1) time.  
This also allows the heap to update the value for a given reference in  
O(log2(N)) time -- very useful for pathfinding algorithms, e.g., which  
keep track of the minimum cost of a the path to various points.

(2) Cython code for finding the minimum cost path through an n-d array  
from any start point(s) to any/all points on the array. The code  
handles boundary conditions properly (and quickly), and can  
(optionally) account for the fact that diagonal moves between elements  
are geometrically longer than axial moves and thus weight the cost of  
the path accordingly. (This implementation, based on Almar's, is  
essentially Dijkstra's algorithm plus the optional distance-weighting.  
It's about an order of magnitude faster than the brute-force path- 
finding algorithm I posted earlier; plus it's not constrained to 2d  
arrays.)

The latter class probably belongs in the imaging scikit, but I figured  
I'd post them both here in case anyone would find them of use. They're  
BSD licensed.

Zach




-------------- next part --------------
A non-text attachment was scrubbed...
Name: mcp.zip
Type: application/zip
Size: 13765 bytes
Desc: not available
Url : http://mail.scipy.org/pipermail/scipy-user/attachments/20091201/a1758be7/attachment-0001.zip 


More information about the SciPy-User mailing list