# [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

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

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

```