Skip to content

Bidirectional Shortest Path

zibon edited this page May 28, 2012 · 3 revisions

###Implementation of Bidirectional Shortest Path Algorithm for pgRouting

Basic Idea

Bidirectional search can speedup finding shortest path by reducing node exploration. In the project I want to implement Bidirectional Dijkstra and Bidirectional A* for pgRouting. I will implement the necessary data structures and the algorithms. I also intend to provide turn restriction support and hierarchical heuristic as nice to have feature.

Links

Project plan as per initial proposal

As I have 12 weeks to complete the project, I like to have a tentative schedule like as follows:

  • Week 1: System study, architecture and data structure design.
  • Week 2-5: Start coding for bidirectional dijkstra. Implement necessary data structure and the algorithm.
  • Week 6-8: Start coding for bidirectional A*. Implement necessary data structures and the algorithm.
  • Week 9: Integration with pgRouting. Implementation of necessary wrapper classes.
  • Week 10-12: Testing, Bug fixing and implementation of nice to have features.
Clone this wiki locally