Skip to content

. implement Bidirectional Dijkstra and use it to compute distances in social networks very quickly; 2. implement A* search algorithm and apply it to compute distances in road networks faster than the classic algorithms do; 3. implement Contraction Hierarchies algorithm and apply it to preprocess large road networks and then compute distances in …

Notifications You must be signed in to change notification settings

Anurag-kuswaha/Advance-Shortest-Path

Repository files navigation

Advance Shortest Path

1. implemented Bidirectional Dijkstra and use it to compute distances in social networks very quickly;

2. implemented A* search algorithm and apply it to compute distances in road networks faster than the classic algorithms do.

    1- Implemented the Single Direction A* alogirthm.                                        ( ## Faster than all)  ( Max time used: 21.91/50.00) 
    2- Implemented the Bidirectional A* alogirthm                                            ( ## slower than 1st)  ( Max time used: 24.32/50.00)
    3- Implemented the Single Direction A* alogirthm with pre-computed potential function    ( ## sloweset of all)  ( ## Max time used: 26.40/50.00) 
 Conclusion- The overall complexity is depending upon calculating the euclid distance as we have to calculate the square root in the euclid distance and Bidirectional A* is   calculating the double the amount of euclid distance as compared to single A* because we have to balance the potential in the Birectional A*.

3. implemented Contraction Hierarchies algorithm and apply it to preprocess large road networks and then compute distances in them much faster;

About

. implement Bidirectional Dijkstra and use it to compute distances in social networks very quickly; 2. implement A* search algorithm and apply it to compute distances in road networks faster than the classic algorithms do; 3. implement Contraction Hierarchies algorithm and apply it to preprocess large road networks and then compute distances in …

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published