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

Download

index.pdf

Date

2004

Author

Hakbilir, Muzaffer

Metadata

Show full item record

Item Usage Stats

152
views

379
downloads

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.

Subject Keywords

Cartography.

URI

http://etd.lib.metu.edu.tr/upload/2/12604949/index.pdf
https://hdl.handle.net/11511/14173

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Generalized bent functions with perfect nonlinear functions on arbitrary groups Yılmaz, Emrah Sercan; Özbudak, Ferruh; Department of Cryptography (2012) This thesis depends on the paper ‘Non-Boolean Almost Perfect Nonlinear Functions on Non- Abelian Groups’ by Laurent Poinsot and Alexander Pott and we have no new costructions here. We give an introduction about character theory and the paper of Poinsot and Pott, and we also compare previous definitions of bent functions with the definition of the bent function in the paper. As a conclusion, we give new theoretical definitions of bent, PN, APN ana maximum nonlinearity. Moreover, we show that bent and PN func...
Improvement in non-linearity of carlet-feng infinite class of boolean functions Khan, Mansoor Ahmed; Özbudak, Ferruh (2012-12-01) In this paper we present a Walsh spectrum based method derived from the genetic hill climbing algorithm to improve the non-linearity of functions belonging to Carlet-Feng infinite class of Boolean functions, without degrading other cryptographic properties they possess. We implement our modified algorithms to verify the results and also present a comparison of the resultant cryptographic properties with the original functions.
Using cost change estimates in a local search heuristic for the pollution routing problem SAKA, Onur Can; Gürel, Sinan; Van Woensel, Tom (2017-03-01) We consider the pollution routing problem (PRP) with deadlines and heterogeneous fleet for which we implement a local search heuristic using inter-route relocate, exchange and intra-route relocate moves. The subproblem of finding optimal speed levels of a truck for a given tour gives optimality properties which relate the marginal speedup costs for each leg on the tour. We use the derived optimality properties and marginal speedup costs to evaluate possible search moves and choose the most promising ones to...
Clustering of manifold-modeled data based on tangent space variations Gökdoğan, Gökhan; Vural, Elif; Department of Electrical and Electronics Engineering (2017) An important research topic of the recent years has been to understand and analyze data collections for clustering and classification applications. In many data analysis problems, the data sets at hand have an intrinsically low-dimensional structure and admit a manifold model. Most state-of-the-art clustering methods developed for data of non-linear and low-dimensional structure are based on local linearity assumptions. However, clustering algorithms based on locally linear representations can tolerate diff...
Impact of physical and chemical heterogeneities on optimal remediation design and costs Aksoy, Ayşegül (null; 2001-01-24) The impact of physical and chemical aquifer heterogeneities on optimal remediation design and costs is investigated by linking a genetic algorithm optimization library with a contaminant transport simulation model. Various levels of physical and chemical (sorption) aquifer heterogeneities are examined. In the first level, heterogeneity is limited to the hydraulic conductivity (K) field. Then systems with heterogeneity in both K and the distribution coefficient (Kd) are considered. The final level of heterog...

Citation Formats

M. Hakbilir, “Implementing the disktra’s algorithm with priority queue to the path finding problem in raster gis,” M.S. - Master of Science, Middle East Technical University, 2004.