The shortest-path problem is an essential component of many applications including Advanced Traveler Information Systems (ATIS), computer networks, etc. A hierarchical routing algorithm decomposes the original graph into a set of fragment graphs and also into a boundary graph which summarizes the fragment graphs. A fully memoized hierarchical routing algorithm pre-computes and stores the shortest-path data structure and the shortest-path-cost data structure for the graph fragments, as well as for the boundary graph. The storage cost of the fully memoized approach can be reduced by a virtual or a hybrid memoization approach, where few or none of the relevant data structures have been pre-computed. This paper achieves two firsts. We use a real graph with 123,000 nodes and 313,000 edges, which is two orders of magnitude larger than the graphs used in related work. Second, the paper analyzes the effect of memoizing individual data structures for the storage overhead and computation time of A*-based hierarchical routing algorithms. Analysis and experiments with the Twin Cities metropolitan road-map show that memoizing the shortest-path-cost data structure for the boundary graph provides the best savings in computation time, for a given amount of storage and a small number of fragments. Memoizing the relevant part of the shortest-path-cost data structure for the fragment graphs provides the next best savings, followed by memoizing the shortest-path data structure for the boundary graph.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A performance analysis of hierarchical shortest path algorithms


    Beteiligte:
    Fetterer, A. (Autor:in) / Shekhar, S. (Autor:in)


    Erscheinungsdatum :

    1997


    Format / Umfang :

    10 Seiten, 17 Quellen




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch





    Dynamic shortest path algorithms for IVHS applications

    Farkas, András, 1965- | DSpace@MIT | 1993

    Freier Zugriff

    Approximate Shortest Path Algorithms for Network-Tree Model

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


    A Shortest Path Algorithm Based on Hierarchical Graph Model

    Wu, Y. / Xu, J. / Hu, Y. et al. | British Library Conference Proceedings | 2003


    A shortest path algorithm based on hierarchical graph model

    Wu Yimin, / Xu Jianmin, / Hu Yucong, et al. | IEEE | 2003