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

Zachary Pincus zachary.pincus@yale....
Wed Nov 25 07:50:00 CST 2009


> I'll send you my current implementation, you should be able to  
> distill something
> usefull from that. The problem is that 1) I make use of another  
> module of
> mine to deal with anisotropic data (because my data is anisotropic)   
> 2) I use
> the MCP method in a specific way, therefore I needed to make the
> implementation more flexible. This makes it less easy to use for  
> other people,
> and thus less handy to include in any toolkit as-is.

Thanks -- I'll see what I can distill!

>>> 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 really mean wrong, sorry. You now select any pixel that is active  
> (meaning
> an arbitrary pixel in the front), and from it calculate the  
> cumulative cost
> for its neighbours. However, it might be that the cumulative cost of  
> this pixel
> is changed later. Therefore you must take the active pixel with the  
> lowest
> cumulative cost; so you know it won't be changed.

Each time a pixel's cumulative cost decreases, I put it back into the  
"active" set (i.e. the front), so then the neighbors get re-examined  
the next iteration, etc. This should suffice, right? Or am I *still*  
missing something? Not that it really matters, because the approach is  
rather inefficient for anything except finding the minimum cost to  
every single array element (and even then I'm not certain this is  
better). But I am curious if I just conceived of the whole problem  
wrong. In which case perhaps I'm not the guy you want implementing  
this for the scikit!

Zach


More information about the SciPy-User mailing list