Determination of shortest path using Dijkstra’s Algorithm for Emergency Service in Kumasi Metropolis

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
It is becoming difficult for emergence services to find the best route especially in Kumasi to any destination in order to save lives in real time. This study deals with the problem of finding shortest paths in traversing some locations within the Kumasi Metropolis in the Ashanti Region of Ghana. Dijkstra’s Algorithm was selected to determine the shortest distances from any location to any destination within the Kumasi metropolis. The objective of thesis is to use Dijkstra’s algorithm in constructing the minimum spanning tree considering the dual carriage ways in the road network of Kumasi metropolis within the shortest possible time for emergence services. The distance between 51 locations of the towns with the major roads was measured and a legend and a matrix were formulated. A visual basic program was prepared using Dijkstra’s algorithm. The distances were used to prepare an input deck for the visual program.The methodology employed included review of relevant literature of the types of Dijkstra’s algorithm and methods employed in the solution of the Dijkstra’s algorithm and to develop computer solutions – ArcGIS and for faster computation of Dijkstra’s algorithm. The result shows a remarkable reduction in the actual distance as compared with the ordinary routing. These results indicate, clearly the importance of this type of algorithms in the optimization of network flows. Hence the shortest distance from any area in Kumasi metropolis to another can easily be calculated using this thesis so as to minimize the average lost of lives in case emergences.
A thesis submitted to the Board of Postgraduate Studies, Kwame Nkrumah University of Science and Technology, Kumasi, in partial fulfilment of the requirements for the award of the Degree of Master of Science in Industrial Mathematics,