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


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Improved shortest path algorithms for transport networks


    Beteiligte:

    Erscheinungsdatum :

    05.04.1977


    Format / Umfang :

    14 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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