[boost] [gsoc2018] Dynamic Shortest Path Tree

Subject: [boost] [gsoc2018] Dynamic Shortest Path Tree
From: a.i_at_[hidden]
Date: 2018-01-17 10:02:42

Hi, I am Donghyuk Kim, a Ph.D. Student at Korea Advanced Institute of Science and Technology. I tried to contribute something last year but was not able to start the project for some reason. So I am about to re-try again this year.

What I would like to contribute is a specific algorithm, "Dynamic Shortest Path Tree" which is simply, a dynamic version of Dijkstra's algorithm.

It is a tree-based data structure to maintain single-source to all destination shortest paths and known to outperform Dijkstra or A* where the insertion and deletion of vertex/edge frequently occur.

The concept of "Dynamic Shortest Path Computation" was originally introduced in 
[Fully Dynamic Algorithms for Maintaining Shortest Paths Trees] by D. Frigioni, et al. 
(http://dl.acm.org/citation.cfm?id=338900) 

I have already implemented a working prototype for my research, but unit test, coding style unification, and much more c++ style modifications are required for the general purpose. 

I hope someone finds it interesting and be a mentor on this journey. 

Thanks in advance.

Best Regards, 
Donghyuk Kim 
a.i_at_[hidden] 

_____________________________________
Sent from http://boost.2283326.n4.nabble.com