<div dir="ltr"><i style=""><span style="font-size:12.8000001907349px">Hi all,</span><br><br><span style="font-size:12.8000001907349px">I've studied performance of olsrd's SPF under different priority queues.</span><br><span style="font-size:12.8000001907349px">We find it quite surprising that in olsrd Dijkstra is based on AVL instead</span><br><span style="font-size:12.8000001907349px">of binary heaps. Different from binary heaps, AVL is not originally intendend</span><br><span style="font-size:12.8000001907349px">as a priority queue. To achieve O(log n) performance, AVL requires nodes with</span><br><span style="font-size:12.8000001907349px">unique key values, which is not reasonable for a priority queues since different</span><br><span style="font-size:12.8000001907349px">nodes can have the same priority. In fact, in the olsrd's SPF, nodes with same</span><br><span style="font-size:12.8000001907349px">priority are put into a list. Then decrase-key procedure can be O(n) in some cases</span><br><span style="font-size:12.8000001907349px">and Dijkstra becomes O(n*n) instead of O(n*logn). Binary heap is the most popular</span><br><span style="font-size:12.8000001907349px">priority queue for Dijkstra, achieving O(n*logn) regardless nodes have the same priority.</span><br><span style="font-size:12.8000001907349px">I put in my github an initial version of binary heaps (BH) for olsrd [1].</span><br><span style="font-size:12.8000001907349px">With traces from a 200-node mesh [2], Dijkstra-BH behaved very similar to Dijkstra-AVL.</span><br><span style="font-size:12.8000001907349px">However, from 800 nodes, Dijkstra-BH drammatically outperformed Dijkstra-AVL.</span><br><span style="font-size:12.8000001907349px">Comments, improvements and bugfixes are welcome,</span><br><br><span style="font-size:12.8000001907349px">thanks in advance.</span><br><br><span style="font-size:12.8000001907349px">[1] <a href="https://github.com/diogomg/olsrd">https://github.com/diogomg/olsrd</a></span><br><span style="font-size:12.8000001907349px">[2] </span><a href="https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets" target="_blank" style="font-size:12.8000001907349px">https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets</a></i><br></div>