forked from pgRouting/pgrouting
-
Notifications
You must be signed in to change notification settings - Fork 0
Bidirectional Shortest Path
zibon edited this page May 22, 2012
·
1 revision
###Implementation of Bidirectional Shortest Path Algorithm for pgRouting
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.
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.