TY - JOUR
AU - Kumar OAM, Santosh
AU - Munapo, Elias
AU - Nyamugure, Philimon
AU - Tawanda, Trust
PY - 2024/09/23
Y2 - 2024/10/14
TI - Path Through Specified Nodes and Links in a Network
JF - Journal of Graphic Era University
JA - JGEU
VL - 12
IS - 02
SE - Articles
DO - 10.13052/jgeu0975-1416.1225
UR - https://riverpublishersjournal.com/index.php/JGEU/article/view/371
SP - 263-282
AB - <p>A constrained shortest route problem in graph theory is about determination of a shortest path between two given nodes of the network that also visits a given set of specified nodes or a set of specified links before arriving to the destination. These earlier approaches did not consider specified elements containing both nodes and links of the given network. This paper finds a shortest path joining the origin node to the destination node, which is constrained to pass through a set of â€˜Kâ€™ specified elements of the given network, where K<sub>1</sub> number of elements represent nodes, 0<K<sub>1</sub><K, and K<sub>2</sub> number of elements represent links, where K<sub>1</sub>+K<sub>2</sub>=K. Alternatively, if the specified elements representing nodes are contained in the set S<sub>n</sub> and the remaining elements representing links by the set S<sub>l</sub>, and the set of specified elements denoted by the set S<sub>e</sub>, then S<sub>e</sub>={S<sub>n </sub>âˆª S<sub>l</sub>}. Such restricted path will also have real-life applications. Depending upon the configuration of the specified elements, these constrained paths may have loops. The approach discussed in this paper is a heuristic approach, which finds the required constrained path in a real time.</p>
ER -