Path Through Specified Nodes and Links in a Network

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 K1 number of elements represent nodes, 0<K1<K, and K2 number of elements represent links, where K1+K2=K. Alternatively, if the specified elements representing nodes are contained in the set Sn and the remaining elements representing links by the set Sl, and the set of specified elements denoted by the set Se, then Se={Sn ∪ Sl}. 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.