| Analysis and Implementation of K-Shortest Path Algorithms in Geographic Information Systems |
||||||||||||||||||||
| Juliana Castillo |
||||||||||||||||||||
| University of Texas at
Dallas |
||||||||||||||||||||
| Master's Project - Spring 2005 |
||||||||||||||||||||
| May 2, 2005 |
||||||||||||||||||||
| ABSTRACT | ||||||||||||||||||||
| This project analyses two algorithms for the k-shortest path problem and implements them in ArcGIS using VBA and ArcObjects. The k-shortest path problem is well-known in the network and graph theory literature and has many applications, yet has never been executed in the context of Geographic Information Systems (GIS). More specifically, this project analyzes the double-sweep and the generalized Floyd algorithms, which are explained in detail. Several data sets are used to test the implementation of k-shortest path algorithms, including a very small test and display network, and two subsets of the road network in the city of Plano, TX. The functionality of the existing k-shortest path algorithms was implemented in ArcGIS, the resulting paths are displayed and the solution times were compared across methods. | ||||||||||||||||||||
| KEYWORDS | ||||||||||||||||||||
| Network analysis, k-shortest path, Double-Sweep Algorithm, Generalized Floyd Algorithm | ||||||||||||||||||||
| CONTENTS | ||||||||||||||||||||
|
||||||||||||||||||||
