[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