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

Gary Ruben gruben@bigpond.net...
Sat Nov 21 18:48:27 CST 2009

```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
>
> 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
```