COMPARISON OF SHORTEST-PATH ALGORITHMS ON LARGE-SCALE ROAD MAPS

Authors
PRINS C
Citation
C. Prins, COMPARISON OF SHORTEST-PATH ALGORITHMS ON LARGE-SCALE ROAD MAPS, RAIRO. Recherche operationnelle, 30(4), 1996, pp. 333-357
Citations number
21
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
RAIRO. Recherche operationnelle → ACNP
ISSN journal
03990559
Volume
30
Issue
4
Year of publication
1996
Pages
333 - 357
Database
ISI
SICI code
0399-0559(1996)30:4<333:COSAOL>2.0.ZU;2-C
Abstract
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.