OPTIMIZED HIERARCHY BASED SHORTEST PATH ALGORITHM FOR ROAD NETWORK GRAPHS
Jagreet Das Gupta · Journal of Mathematical Sciences & Computational Mathematics · 2020
Efficiently determining Shortest Paths on Road Maps has been a heavily engineered function for many routing apps like Google Maps & Yandex Maps for years now. Dutch computer scientist, Edsger W. Dijkstra set the stepping stone by formulating the now famous, Dijkstra’s algorithm for shortest paths. Later it was improved upon by newer algorithms like A*. We introduce a way to implement modern algorithms such as Contraction Hierarchy, Highway Hierarchy and PHAST Algorithm to find optimal shortest paths in real life scenario road maps. It bases heavily on constructing a virtual “highway” which the shortest path should pass through theoretically as they are heavily traversed in real life generally. It considers parameters such as Road Distance between nodes(Edge Weight), Importance Factor during Contraction Hierarchy Phase, Cartesian Distance From Target, External Real Time Factors like Weather and Traffic. We determine a Heuristic Function using the above parameters and then use that to run a Bi-Directional PHAST based A* from both the source and the target node and then determine the shortest path once a common highway exists in both directional search’s settled vector or a fallback stage is reached.