Abstract: Querying for the shortest path from a source vertex to a sink vertex in real time is a fundamental problem in numerous applications. Several lower-bounding schemes have been proposed to solve the problem so far, such as A* search and ALT algorithm. But these schemes adopted loose valuations on distance so that there are great potentialities for improving the lower bounds. A novel two-stage goal directed lower-bounding approach, called ACT algorithm, was proposed, which combined A* search, centers and triangle inequality with no prior domain knowledge. Unlike previous schemes, the new algorithm can obtain excellent distance bounds by exploiting a large number of pre-computed data. The experimental results on real road networks show that ACT algorithm significantly outperforms all previous algorithms. In some instances, the vertices scanned by ACT algorithm are only about 25% more than those on optimal paths.