I am Donghyuk Kim, a Ph.D. Student at KAIST(Korea Advanced Institute of Science and Technology) in South Korea.
I've been studying motion/path planning algorithm and I'd like to contribute to a specific algorithm,
"Dynamic Shortest Path Computation" in Boost graph library as a google summer code project.
It is a tree-based data structure for maintaining single-source to all destination shortest path. It is also known that it outperforms the recomputation of Dijkstra or A* where insertion and deletion of vertex/edge can frequently happen.
Most of my source codes (research/project-purpose things) are in a private repository by our policy, for this reason, the only thing I can share is the below one:
The concept of "Dynamic Shortest Path Computation" was originally introduced in
[Fully Dynamic Algorithms for Maintaining Shortest Paths Trees] by D. Frigioni, et al.
I've already implemented a prototype for my research, but testing, coding style unification and much more c++ style modification are required for general purpose.
I hope someone find it interesting and be a mentor in this journey.
On 22/03/2017 03:50, A.I via Boost wrote:
> I've been studying motion/path planning algorithm and I'd like to contribute
> to a specific algorithm,
> "Dynamic Shortest Path Computation" in Boost graph library as a google
> summer code project.
Would anybody be willing to mentor this project in Boost.Graph? We
likely will have plenty of available slots this year.