The problem addressed in this paper is how to efficiently compute the approximate shortest paths of large-scale network. We propose the wholly new network-tree model (NTM) constructed from arbitrary network and associated approximate algorithms for high performance computation of shortest path in large-scale network. For the tradeoffs between the computational speed and errors, three approximate network-tree shortest path (ANTSP) algorithms are presented: nearest ANTSP, heuristic ANTSP and sub-optimal ANTSP algorithms. The experiment results based on grid network show that all ANTSP algorithms achieve much higher computational efficiency than Dijkstra algorithm, and the average errors of heuristic ANTSP and sub-optimal ANTSP algorithms are significantly reduced.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Approximate shortest path algorithms for network-tree model


    Beteiligte:
    Guozhen Tan, (Autor:in) / Xiaojun Han, (Autor:in) / Yilin Zhao, (Autor:in)


    Erscheinungsdatum :

    01.01.2003


    Format / Umfang :

    1440240 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Approximate Shortest Path Algorithms for Network-Tree Model

    Tan, G. / Han, X. / Zhao, Y. et al. | British Library Conference Proceedings | 2003


    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

    Dual Shortest-Path Tree: Ideas and Methods

    National Research Council (U.S.) | British Library Conference Proceedings | 2005


    Optimizing Drone Navigation Using Shortest Path Algorithms

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