Algoritmo de reducción de grafos para búsqueda de camino mínimo en Sistemas de Información Geográfica (Graph-reduction algorithm for finding shortest path in Geographic Information Systems)

Rafael Rodríguez-Puente (, Manuel S. Lazo-Cortés (

Universidad de las Ciencias Informáticas
This paper appears in: Revista IEEE América Latina

Publication Date: Dec. 2012
Volume: 10,   Issue: 6 
ISSN: 1548-0992

Geographic Information Systems are computer systems that are used to store and manipulate information closely related to its geographical position. This technology has developed so rapidly in the past two decades that is already accepted as an essential tool for effective use of such information. An application of Geographic Information System is the shortest path search between two locations. The problem solved in this paper is to present a road network of a map (all objects) through a graph for subsequente network analysis, specifically for finding the shortest path and respond quickly to the users. We propose an algorithm for reducing a graph and an algorithm for searching shortest path in the reduced graph by the proposed algorithm. These results can be subsequently applied to Geographic Information Systems.

Index Terms:
Geographic Information Systems, Shortest path problem, Network theory (graphs), Graph grammars, Graph reduction   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (451)]