Trust Tawanda
Department of Statistics and Operations Research, National University of Science and Technology, Bulawayo, Zimbabwe.

Elias Munapo
School of Economics and Decision Sciences, North West University, Mafikeng Campus Mafikeng, South Africa.

Santosh Kumar
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia.

Philimon Nyamugure
Department of Statistics and Operations Research, National University of Science and Technology, Bulawayo, Zimbabwe.

DOI https://doi.org/10.33889/IJMEMS.2023.8.5.057

  ;

Abstract

Shortest path problem (SPP) has various applications in areas such as telecommunications, transportation and emergency services, and postal services among others. As a result, several algorithms have been developed to solve the SPP and related problems. The current paper extends the TANYAKUMU labelling method for solving the Travelling salesman problem (TSP) to solve SPP in directed transportation networks. Numerical illustrations are used to prove the validity of the proposed method. The main contributions of this paper are as follows: (i) modification of TSP algorithm to solve single source SPP, (ii) the developed method numerically evaluated on four increasingly complex problems of sizes 11×11, 21×21, 23×23 and 26×26 and lastly (iii) the solutions obtained from solving these four problems are compared with those obtained by Minimum incoming weight label (MIWL) algorithm. The proposed algorithm computed the same shortest paths as the MIWL algorithm on all four problems.

Keywords- TANYAKUMU labelling method, MIWL algorithm, Shortest path problem, Transportation network.

Citation

Tawanda, T., Munapo, E., Kumar, S., & Nyamugure, P. (2023). Extended TANYAKUMU Labelling Method to Compute Shortest Paths in Directed Networks. International Journal of Mathematical, Engineering and Management Sciences, 8(5), 991-1005. https://doi.org/10.33889/IJMEMS.2023.8.5.057.