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

Almar Klein almar.klein@gmail....
Wed Nov 25 08:05:02 CST 2009


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

Ah, now I see. I'm sorry. Yes, your code should produce the correct result,
although it will probably evaluate a lot of pixels more than once :)

Almar


More information about the SciPy-User mailing list