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

Almar Klein almar.klein@gmail....
Wed Nov 25 06:16:18 CST 2009

```Hi,

I have an implementation of the Minimum Cost Path method too. It uses
a binary heap to store the
active pixels (I call it the front). Therefore it does not need to
iterate over the the whole image at
each iteration, but simply pops the pixel with the minimum cumulative
cost from the heap. This
significantly increase speed.

Because I am still changing stuff to my MCP implementation, and I use
it for my research, I am a bit
reluctant to make it publicly available now. I'd be happy to share the
binary heap implementation though.

Looking at the posted code, I think it is incorrect. Each iteration,
you should only check the neighbours
of the pixel that has the minimum cumulative costs. That's why the
binary heap is so important to get
it fast.

I short while ago I made a flash app with some examples. It also
contains the pseudo code, although
I use a slighly different terminology (cost=speed, cumulative cost=time):
http://dl.dropbox.com/u/1463853/mcpExamples.swf

Here's a snipet of how I use the binary heap:
=====
from heap cimport BinaryHeapWithCrossRef
front = BinaryHeapWithCrossRef(frozen_flat)
value, ii= front.Pop()  # to get the pixel of the front with the
minimum cumulative cost
front.Push(cumcost_flat[ii], ii)  #  to insert or update a value
=====
I use flat arrays and scalar indices, so I need to store only one
reference per pixel. This also
makes the implementation work for 3D data (or even higher dimensions
if you wish).
frozen_flat is a flat array, the same size as the imput (cost or
speed) image, that keeps track
whether pixels are frozen (indicating they wont change). A pixel is
frozen right after it is popped
from the heap.  I use the same array in the heap to be able to update
values if a pixel is already
in the heap.

I hope this helps a bit. If not, feel free to ask.

Almar

2009/11/22 Stéfan van der Walt <stefan@sun.ac.za>:
> 2009/11/22 Stéfan van der Walt <stefan@sun.ac.za>:
>> This code looks really handy, and I'd love to add it.  Would you
>> consider putting your code in a branch on github?
>
> Actually, don't worry -- I'll add it quickly.  Thanks for the contribution!
>
> Cheers
> Stéfan
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: heap.pxd
Type: application/octet-stream
Size: 1181 bytes
Desc: not available
Url : http://mail.scipy.org/pipermail/scipy-user/attachments/20091125/77dfe36a/attachment-0002.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: heap.pyx
Type: application/octet-stream
Size: 26346 bytes
Desc: not available
Url : http://mail.scipy.org/pipermail/scipy-user/attachments/20091125/77dfe36a/attachment-0003.obj
```