solution

MINIMAL PATH PROBLEM (SHORTEST ACYCLIC ROUTE MODELS) The travelling salesman problem is a routing problem involving rather severe constraints. Another routing problem arises when we wish to go from one place to another or to several other places and we are to select the shortest route (involving least distance or time or cost) out of many alternatives, to reach the desired station. Such acyclic route network problems can be easily solved by graphical method. A network is defined as a set of points or nodes which are connected by lines or links. A way of going from one node (the origin) to another (the destination) is called a route or path. The links in a network may be one way (in either direction) or two way (in both directions). The numbers on the links in the network represent the time, cost or distance involved in traversing them. It is assumed that the way in which we enter a node has no effect on the way of leaving it-an assumption which does not hold good in travelling salesman problem EXAMPLE 5.10-1 20 f55 20 50 20 10 30 20 40 10 20 30 50 30 10 10 30 d 10 30 40 9) 40 0 20 20 40 (h Fig. 5.8 A person wishes to reach the destination ‘k while starting from the station a’in the network