[Olsr-dev] Improving SPF with binary heaps
Fri Jul 10 13:17:31 CEST 2015
On Thu, Jul 9, 2015 at 9:32 PM, Diogo Gonçalves
> Hi all,
> I've studied performance of olsrd's SPF under different priority queues.
> We find it quite surprising that in olsrd Dijkstra is based on AVL instead
> of binary heaps. Different from binary heaps, AVL is not originally
> as a priority queue. To achieve O(log n) performance, AVL requires nodes
> unique key values, which is not reasonable for a priority queues since
> nodes can have the same priority. In fact, in the olsrd's SPF, nodes with
> priority are put into a list. Then decrase-key procedure can be O(n) in some
> and Dijkstra becomes O(n*n) instead of O(n*logn). Binary heap is the most
> priority queue for Dijkstra, achieving O(n*logn) regardless nodes have the
> same priority.
> I put in my github an initial version of binary heaps (BH) for olsrd .
> With traces from a 200-node mesh , Dijkstra-BH behaved very similar to
> However, from 800 nodes, Dijkstra-BH drammatically outperformed
> Comments, improvements and bugfixes are welcome,
I had a short look at "heap.h"... are all of these functions called
from the user of the heap, even things like "swap_left" and
I am also quite unsure what I use "heap_decrease_key" and "heap_increase_key".
How do I remove things from a heap (I don't see a remove function) ?
More information about the Olsr-dev