COMPUTER IMPLEMENTATION TO FIND THE SHORTEST PATH SUBJECTED TO SIDE CONSTRAINTS

Abstract

In a network a rooting problem consists of finding a path between two or more nodes which 08ximiSes or minimises some measure of p2rfnr0ance along the p8th4 A number of different constraints may be placed on acceptable paths or the arcs may have several measures of performance. As these measures can not be converted to only one measore, it is necessary to optimise the path keep in in view other measures of performance or the other performances along the path may be constrained. In this presentation an algorithm 8 a software package has been developed to rind the shortest path from are node (called source node or origin node) to another node (called sink node or terminal nodg) in a network which is having side constraints on arcs, Direct Dynamic Programing principle has been applied making extensive use of sophisticated data structures for staring the network data managing the labels and facilitating the alSorithm^ The developed algorithm has been tested on various set of random data to see 1t 's computational efficiency