Shortest path problem dijsktra with arc flags

Question

On large graphs like 2M node road network, dijkstra can not solve shortest path problem in suitable time. We need to shortest path query execution time under 1 second and I am implementing arc flag way to make dijkstra fast. Is there anybody know about how to implement arc flags preprocessing and query. Preprocessing of arc flags has some different algorithm I need fast one.

Answer 1

Have you tried A*? It's a refinement of Dijkstra's algorithm that typically performs better; moreover, you can tune it to prefer search speed over optimality if that is an option.