In this paper we review the algorithms available for computing shortes
t paths in large sparse graphs with non-negative weights. We then pres
ent the results of a study comparing efficient PC-based implementation
s, executed on large road-like networks. Some algorithms are up to 218
times faster than Dijkstra's classical algorithm when run on graphs w
ith 15000 nodes.