COMPARATIVE ANALYSIS AND IMPLEMENTATION OF DIJKSTRA'S SHORTEST PATH ALGORITHM FOR EMERGENCY RESPONSE AND LOGISTIC PLANNING

  • AH Eneh DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF NIGERIA, NSUKKA, ENUGU STATE, NIGERIA.
  • UC Arinze DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF NIGERIA, NSUKKA, ENUGU STATE, NIGERIA.
Keywords: TransRoute, shortest path algorithms, double bucket data structure, GIS

Abstract

TransRoute: a web-based vehicle route planning application is proposed in this paper. This application leverages existing input-output (I/O) efficient implementations of shortest path algorithms (SPAs) to implement the proposed system that will fundamentally address the problems experienced in moving people, goods and services from one location to another. A number of SPAs are evaluated using landau notations. Main functionalities of the system will be implemented as a web-enabled geographic information system (GIS) application based on open-source technologies and object-oriented software development methodology using unified modeling language. Pilot implementation is done based on spatial data of three selected states in Nigeria, pulled from web-based mapping tools like Google Maps and Microsoft Bings respectively. In conclusion, the Dijkstra's algorithm implemented with double bucket dynamic data structure is selected for implementing the proposed route planning system, as past research efforts has proven that it is the fastest with run-time improvements from O(m + n/log C) to O(m) respectively.

 

http://dx.doi.org/10.4314/njt.v36i3.30

Published
2017-06-30
Section
Computer, Telecommunications, Software, Electrical & Electronics Engineering

Journal Identifiers


eISSN: 2467-8821
print ISSN: 0331-8443