Hassan Karimi
MCNC
P.O. Box 12889
Research Triangle Park, NC 27709-2889
karimi@mcnc.org
Abstract
Geographic information systems (GISs) use optimal routing algorithms to solve problems in transportation, hydrology, navigation, rescue and mission, and others. Of the many routing algorithms available, Dijkstra's algorithm is one of the most widely used for computing best paths in GISs. Dijkstra's algorithm guarantees best solutions with a time complexity of O(n2) in the worst case. This time complexity results in very long processing times for computing best paths in large networks, which can be a serious problem for real-time applications. Therefore, alternative algorithms that can handle the real-time processing of optimal routing in GISs are needed. In this paper, alternative optimal routing algorithms for real-time GIS applications are discussed.