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

[Zachary Pincus]

Hi Almar,

The binary heap code looks extremely useful in general -- thanks for  
making it available! Do you have any license you want it under? (BSD  
seems preferable if this is to be incorporated into a scikit, e.g.)

It would be great if you would be interested in making your MCP code  
available too, even just as a base for others to hack on a bit (rather  
than as a finished contribution), but this is of course up to you.  
Otherwise I'll probably try to throw together something similar using  
the heap code.

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


Incorrect means that the code might give a wrong result: is this the  
case? I *think* I had satisfied myself that the implementation (while  
suboptimal because it does extra work -- a lot in some cases!) would  
yield the correct path. (Note that the code doesn't terminate when the  
"end" pixel is first assigned a cost, but when no costs are changing  
anywhere. Basically, brute-force search instead of Dijkstra's  
algorithm. Again, while a lot more than necessary to just find the  
minimum cost to a single point, this condition should be sufficient to  
ensure that the minimum cost to *every* point in the array has been  
found, right? If my analysis is wrong, though, it wouldn't be the  
first time!)


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


Do you have code to take the flat index and the shape of the original  
array and return the indices to the neighboring pixels, or is there  
some other trick with that too?

Anyhow, thanks for your suggestions and contribution! I look forward  
to making use of the heap.

Best,
Zach


On Nov 25, 2009, at 7:16 AM, Almar Klein wrote:

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