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%.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Improved shortest path algorithms for transport networks


    Contributors:

    Publication date :

    1977-04-05


    Size :

    14 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Shortest Path Algorithms: An Evaluation using Real Road Networks

    Zhan, F. B. / Noon, C. E. | British Library Online Contents | 1998



    Optimizing Drone Navigation Using Shortest Path Algorithms

    Girijalaxmi / Houde, Kavita V. / Hegadi, Ravindra S. | Springer Verlag | 2024



    The Shortest Path Problem with Uncertain Information in Transport Networks

    Neumann, Tomasz | British Library Conference Proceedings | 2016