A* with Perfect Potentials

Quickly determining shortest paths in networks is an important ingredient for many routing applications. While Dijkstra's algorithm can be used to solve these problems, it is too slow for many practical problems. A* is an extension to Dijkstra's algorithm. It uses a potential function to estimate the distance of each node to the target. By adding these estimates to the queue keys, the search is directed towards the target. The quality of this potential determines the performance of A*. We introduce a novel way to efficiently calculate perfect potentials for extended problem settings where a lower bound graph is available. For example, in the case of routing with live traffic, this could be the free flow graph.