Identification of Optimum Shortest Path using Multipath Dijkstra’s Algorithm Approach

Kumari Pritee, Garg R.D., (doi: 10.23953/cloud.ijarsg.321)

Abstract


Many route mappings were done with the help of API of Google maps but do not provide geospatial Routing functionality like overlay, interpolation etc. This project aims to find the shortest path between two or more points by using multipath Dijkstra’s algorithm via PgRouting. Dijkstra’s algorithm provides advantages on time required for selecting the network and building graph over the algorithm speed. In that case, A-star is always preferred over Dijkstra’s algorithm. Dijkstra’s algorithm has a computational complexity of O (n2) with a network consisting of n nodes. This Project explains the steps to prepare the data by converting shape files into SQL files and import it into PostgreSQL/PostGIS, make routing topology, indexes, and queries, dynamically assign costs by PgRouting, and write a custom function ‘plpgsql’ using PL/pgSQL (Procedural programming structured query language) supported by PostgreSQL. This report provides all geospatial functions with dynamic support via PgRouting which allows many clients, like Quantum GIS and Udig, represents client visualization for modification of data and attributes for instantly reflecting changes via PgRouting. PgRouting Provides a framework by which cost parameters are calculated dynamically. This paper specifies the routing of Varanasi city roads using Dijkstra’s algorithm and PgRouting. This article focuses on dynamic routing on the complex network like Varanasi City over the web mapping application so that Client can easily find their shortest route along with Cost parameters.


Keywords


Dijkstra’s algorithm; Geographic information system; PostgreSQL/PostGIS; PgRouting; GeoServer; Web services

Full Text: PDF

Refbacks

  • There are currently no refbacks.




Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

*2016 Journal Impact Factor was established by dividing the number of articles published in 2014 and 2015 with the number of times they are cited in 2016 based on Google Scholar, Google Search and the Microsoft Academic Search. If ‘A’ is the total number of articles published in 2014 and 2015, and ‘B’ is the number of times these articles were cited in indexed publications during 2016 then, journal impact factor = A/B. To know More: (http://en.wikipedia.org/wiki/Impact_factor)