Using RWQ to improve Dijkstra's SSSP algorithm
During my 6month sabbatical (July - Dec 2007), the first piece of research
work I have undertaken is an investigation of improving the performance of Dijkstras shortest path algorithm. Traditionally, fib heaps form part of the algorithm. Instead, I am applying the data structure: relaxed weak queues (RWQ), a far more complex implementation, but one that promises better performance.
Fib heaps and RWQ are priority queues. The first part of my study is a PES simluation of event sets. This is a popular way to compare priority queues.
Progress:
- July 07: implemented and tested RWQ and fib heap C++ code (planning to release the code here)
- July 07: generation of PES experiemental data (runtime measured on a mac computer to billions of a second accuracy)
- prelim results: surprisingly big difference in the runtime fib heap extractmin() verses RWQ extractmin(), much more than was expected!
- * July 07: analysis and presenting the data in a conf paper