Dijkstra's algorithm is considered for the single source single target shortest path problem in large sparse graphs. The goal is to reduce the response time for on-line queries by using precomputed information. Due to the size of the graph, preprocessing space requirements can be only linear in the number of nodes. It is assumed that a layout of the graph is given. In the preprocessing, It is determined from this layout a geometric object for each edge containing all nodes that can be reached by a shortest path starting with that edge. Based on these geometric objects, the search space for on-line computation can be reduced significantly. Shortest path queries can then be answered by Dijkstra's algorithm restricted to edges where the corresponding geometric object contains the target. It is presented an extensive experimental study comparing the impact of different types of objects. The test data are real-world traffic networks, the typical field of application für this scenario. Furthermore, new algorithms are presented as well as an empirical study for the dynamic case of this problem, where edge weights are subject to change and the geometric containers have to be updated. The quality and the time for different update strategies are evaluated that guarantee correct shortest paths. Finally, a software framework is presented in C++ to realise the implementations of all of our variants of Dijkstra's algorithm. A basic implementation of the algorithm is refined for each modification and - even more importantly - these modifications can be combined in any possible way without loss of efficiency.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen


    Exportieren, teilen und zitieren



    Titel :

    Geometric shortest path containers


    Weitere Titelangaben:

    Der geometrisch kürzeste Lieferweg


    Beteiligte:


    Erscheinungsdatum :

    2004


    Format / Umfang :

    23 Seiten, 6 Bilder, 1 Tabelle, 48 Quellen



    Medientyp :

    Report


    Format :

    Print


    Sprache :

    Englisch




    Geometric k shortest paths

    Suri, Subhash / Eriksson-Bique, Sylvester / Hershberger, John et al. | BASE | 2015

    Freier Zugriff

    Urban K shortest path obtaining method based on shortest path tree

    DING JIANXUN / YANG BEINUO / DUAN RUI et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Shortest safe path planning for vehicles

    Lambert, A. / Bouaziz, S. / Reynaud, R. | IEEE | 2003


    A Multiple Pairs Shortest Path Algorithm

    Wang, I.-L. / Johnson, E. L. / Sokol, J. S. | British Library Online Contents | 2005


    Shortest path using detour heuristic algorithm

    Wu, Shu-Hui / Wang, Shu-Jen / Tai, Chien-Ting et al. | Tema Archiv | 1999