Abstract The three most appropriate algorithms for calculating shortest paths in transport road networks—those due to Moore, D'Esopo and Dijkstra—are examined using CPU times on five realistic networks as criteria. Their relative efficiencies are shown to depend on certain characteristics of the network. In approximate order of importance these are: the network size (in terms of the number of nodes, N nodes, and/or links, N links), the mean link length d̄ (in terms of the number of integer units), the coefficient of variation of the link lengths, the shape of the network and the ratio of links to nodes. Quantitative rules covering the first two factors have been derived indicating that the fastest algorithm will be: (1) Dijkstra for networks where d̄/N nodes<c 1; (2) Moore if N nodes<c 2; (3) D'Esopo under all other conditions. c 1 and c 2 are parameters ∼0.02 and 75 respectively for FORTRAN IV programs on an ICL 1906A; these values are expected to vary from one computer installation to another. Qualitative guidelines as to the effect of the other three factors are given. A number of suggestions are also made for improved network data structures and for reducing the size of the network prior to calculating shortest paths. Both are applicable to any of the basic algorithms considered and, taken together, can reduce CPU times by up to 40%.
Improved shortest path algorithms for transport networks
1977-04-05
14 pages
Article (Journal)
Electronic Resource
English
Shortest Path Algorithms: An Evaluation using Real Road Networks
British Library Online Contents | 1998
|Shortest Path Algorithms: An Evaluation using Real Road Networks
Online Contents | 1998
|Optimizing Drone Navigation Using Shortest Path Algorithms
Springer Verlag | 2024
|The Shortest Path Problem with Uncertain Information in Transport Networks
Springer Verlag | 2016
|The Shortest Path Problem with Uncertain Information in Transport Networks
British Library Conference Proceedings | 2016
|