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

Almar Klein almar.klein@gmail....
Wed Nov 25 07:06:57 CST 2009


Hi Zach,

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

BSD's fine :)

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

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.

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

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

Yes, it's in the code I'll send you.


Cheers,
  Almar


More information about the SciPy-User mailing list