[ccan] [PATCH 2/5] aga,agar: Dijkstra's algorithm

[David Gibson]

On Thu, Nov 12, 2015 at 04:59:51PM -0500, Emilio G. Cota wrote:
> On Thu, Nov 12, 2015 at 22:42:45 +1100, David Gibson wrote:
> > This uses the lpq module as the implementation of the priority queue.  That
> > means this implementation is some way behind the theoretical efficiency of
> > Dijkstra's algorithm.  It should be reasonably straightforward to swap out
> > the priority queue for a better one in the future, though.
> 
> Have you considered using the heap module?

The aga module (unlike agar) isn't supposed to allocate memory,
instead using the structures that the caller embeds in their own data
structures.

Unfortunately, that means it's not possible to use a binary heap - at
least not the usual array based implementation.  You could make a link
only based implementation, but it gets so horrible that you might as
well use a better data structure (e.g. a pairing heap) at that point.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20151113/496efbda/attachment.sig>