Shortest Transportation Route Network in Nigeria Using Floyd-Warshall’s Algorithm

Abstract

This study presents the application of Floyd – Warshall algorithm, which is an all pairs shortest path algorithm in finding the shortest route network for major cities in Nigeria. Twenty one (21) city route networks in Nigeria showing distances (km) are considered with Calabar, Cross River State as the origin node and Kaduna, Kaduna State as the sink node. Distance and precedence matrices are computed for all iterations to obtain the weight between nodes in the network and the shortest route respectively. The optimal route for all pairs in the network and the total distance travelled from one node to another are obtained respectively from the precedence and distance matrices of the final iteration. Detailed results showed that the algorithm is efficient. The designed route network shows the shortest route for all pairs of nodes in the network and also exposes hidden shortest routes. These routes are recommended for inter-city transportation in Nigeria.

Keywords: Floyd-Warshall algorithm, optimal shortest path, shortest distances, route determination