The classic problem of finding the shortest path over a network has be
en the target of many research efforts over the years. These research
efforts have resulted in a number of different algorithms and a consid
erable amount of empirical findings with respect to performance. Unfor
tunately, prior research does not provide a clear direction for choosi
ng an algorithm when one faces the problem of computing shortest paths
on. real road networks. Most of the computational testing on shortest
path algorithms has been based on randomly generated networks, which
may not have the characteristics of real road networks. In this paper,
we provide an objective evaluation of 15 shortest path algorithms usi
ng a variety of real road networks. Based on the evaluation, a set of
recommended algorithms for computing shortest paths on real road netwo
rks is identified. This evaluation should be particularly useful to re
searchers and practitioners in operations research, management science
, transportation, and Geographic Information Systems.