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

[Gary Ruben]

Hi Zach,

I haven't looked at your code, but your description sounds like you've 
got a very nice solution. When you originally asked this, I immediately 
thought of Lee's algorithm, or Jarvis's distance-transform based path 
planning, which uses a modified distance transform that fixes the start 
and goal point costs. I didn't mention them because they don't cover to 
your case, but I think your solution is a more general case or theirs - 
i.e. you can use yours for navigation/maze solving by setting the 
obstacle/wall values to something greater than the maximum distance to 
the goal and the floor values to 0.

I think would be a very nice, general routine for scikits.image,

Gary R.

Zachary Pincus wrote:
> 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
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user