Implementing the disktra's algorithm with priority queue to the path finding problem in raster gis

Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Turkey

Approval Date: 2004

Thesis Language: English

Student: Muzaffer Hakbilir



Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Prefering raster or vector GIS is more a question of choice than of accuracy. A raster-based GIS model shows a better fit, when the problem is concerned with finding a path across terrain which does not have predefined paths. The approach of this study is to translate the scenario into a ءleast-cost path̕ graph with an associated cost function on the raster-based GIS layer. Sometimes, computation of shortest paths between different locations on a raster-based GIS has to be done in real-time. Therefore, knowing which shortest path algorithm runs fastest on real networks is needed. In order to meet this requirement, Dijsktra̕s algorithm with priority queue implementation is selected, because it reduces the time complexity of Dijsktra̕s algorithm from O(V2 log V) to O(E log V ). The run-time results of Dijsktra̕s algorithm, Dijsktra̕s algorithm with priority queue implementation and ArcMap Spatial Analyst Tool are compared for a number of raster GIS layers which have different number of nodes. Dijsktra̕s algorithm with priority queue implementation and Spatial Analyst tool of ArcMap show a linear relationship between node numbers and time, whereas Dijsktra̕s algorithm represents a quadratic relationship. Hence, when the number of nodes and edges in graph is increased, the run-time performance of the Dijsktra̕s algorithm decreases rapidly.