[gsoc2018] Dynamic Shortest Path Tree
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@acm.org _____________________________________ Sent from http://boost.2283326.n4.nabble.com
Hi everyone,
this could be a potential interesting GSoC
Anyone to mentor ?
Cheers,
David
On Wed, Jan 17, 2018 at 10:02 AM, A.I via Boost
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@acm.org
_____________________________________ Sent from http://boost.2283326.n4.nabble.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost
participants (2)
-
a.i＠acm.org -
David Bellot