Extended TANYAKUMU Labelling Method to Compute Shortest Paths in Directed Networks
Résumé
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.
Citer ce document
Exporter : BibTeX · RIS (Zotero, Mendeley, EndNote)
Accès au document
Texte intégral archivé sur SPHAERO, en accès ouvert : lisible gratuitement en ligne après connexion. Le document reste aussi disponible à sa source. Se connecter
Voir l'article sur le site de la revueLicence et provenance
Licence : CC BY
Notice moissonnée depuis OpenAlex le 27/09/2026. Le document reste hébergé par sa source.
Voir le document à la source →