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

Zachary Pincus zachary.pincus@yale....
Sat Nov 21 15:52:48 CST 2009


OK, here's what I have. Not Dijkstra's algorithm, but very simple and  
not bad for many purposes.

You pass in a 2D costs array, start- and end-points, and a maximum  
number of iterations; the code then keeps track of the minimum  
cumulative cost to each pixel from the starting point, as well as the  
path thereto. It does this by keeping track of "active" pixels -- any  
time a lower cumulative cost to a given pixel is found, that pixel is  
made active. Each iteration, all the neighbors of the "active" pixels  
are examined to see if their costs can be lowered too. Basically  
breadth-first search.

Limitations and oddities:
- Currently, diagonal and vertical/horizontal steps are both allowed.  
Easy enough to make this a parameter.
- Paths along the boundary aren't traced out because I didn't want to  
deal with an if-check in the inner loop to make sure that the x,y  
position plus the current offset wasn't out of bounds. This could be  
addressed by (a) padding the input array by one pixel on each side,  
(b) putting the if in the inner loop, or (c) having a second pass  
through the edge pixels.
- In theory, the code could find the cheapest path from top-left to  
bottom-right in a single pass because "active" pixels are marked  
immediately as the code iterates through the array. So the max_iters  
parameter doesn't guarantee that paths longer than that will not be  
found. But it does guarantee that any path found less than that length  
is optimal...

Let's say it's BSD licensed, in case anyone finds it of use.

Zach


-------------- next part --------------
A non-text attachment was scrubbed...
Name: trace_path.zip
Type: application/zip
Size: 1263 bytes
Desc: not available
Url : http://mail.scipy.org/pipermail/scipy-user/attachments/20091121/c38b059c/attachment.zip 
-------------- next part --------------



More information about the SciPy-User mailing list