[SciPy-User] Dijkstra's algorithm on a lattice

Zachary Pincus zachary.pincus@yale....
Sat Nov 21 09:06:57 CST 2009


> 2009/11/19 Zachary Pincus <zachary.pincus@yale.edu>:
>> A bit off-topic, but before I write some C or cython to do this, I
>> thought I'd ask to see if anyone knows of existing code for the task
>> of finding the shortest (weighted) path between two points on a  
>> lattice.
>
> This is what the shortest path routine in scikits.image is meant to
> do.  How can we modify it to make it more useful to you?

Hi Stéfan,

Based on just a rudimentary perusal of that code, I thought it only  
found the lowest-cost path from the left to the right of an array...  
is this still the case? I'd been needing something to go from an  
arbitrary point to any other arbitrary point.

I just started working on some cython code that will compute the  
shortest path (under a given length) from any point to any other. It's  
not quite Dijkstra (for which one needs to keep a sorted list of the  
next pixels to visit), but more like breadth-first search to a given  
depth. I'll be happy to send it over if that sort of thing sounds  
useful.

Zach


More information about the SciPy-User mailing list