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

Authors

  • 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.

DOI:

https://doi.org/10.4314/njt.363.1404

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

Downloads

Published

2017-06-30

Issue

Section

Computer, Telecommunications, Software, Electrical & Electronics Engineering

How to Cite

COMPARATIVE ANALYSIS AND IMPLEMENTATION OF DIJKSTRA’S SHORTEST PATH ALGORITHM FOR EMERGENCY RESPONSE AND LOGISTIC PLANNING. (2017). Nigerian Journal of Technology, 36(3), 876-888. https://doi.org/10.4314/njt.363.1404