COMPARATIVE ANALYSIS AND IMPLEMENTATION OF DIJKSTRA'S SHORTEST PATH ALGORITHM FOR EMERGENCY RESPONSE AND LOGISTIC PLANNING
DOI:
https://doi.org/10.4314/njt.363.1404Keywords:
TransRoute, shortest path algorithms, double bucket data structure, GISAbstract
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.
Downloads
Published
Issue
Section
License
The contents of the articles are the sole opinion of the author(s) and not of NIJOTECH.
NIJOTECH allows open access for distribution of the published articles in any media so long as whole (not part) of articles are distributed.
A copyright and statement of originality documents will need to be filled out clearly and signed prior to publication of an accepted article. The Copyright form can be downloaded from http://nijotech.com/downloads/COPYRIGHT%20FORM.pdf while the Statement of Originality is in http://nijotech.com/downloads/Statement%20of%20Originality.pdf
For articles that were developed from funded research, a clear acknowledgement of such support should be mentioned in the article with relevant references. Authors are expected to provide complete information on the sponsorship and intellectual property rights of the article together with all exceptions.
It is forbidden to publish the same research report in more than one journal.