please give detailed information

5.9 PROBLEMS RELATED TO SEQUENCING (ROUTING PROBLEMS IN NETWORKS) Routing problems in networks are the problems related to sequencing and, of late, they have been receiving increased attention. Such problems usually occur in the areas of transportation and communication. A network problem involves the determination of a route from city i (origin) to city i (destination) for which there exist a number of alternative paths at various stages of the journey. The cost of journey, which may be function of distance, time or money, is different for different routes and the problem is to find the minimum cost route. Theoretically, the procedure involves determination of the cost of all the possible routes and selecting the one with minimum cost. However, in actual practice the number of such feasible alternatives is too large to be tried one by one. For instance, with 6 alternative paths, the number of possibilities is 51 = 120, with 9 paths the number becomes 8! = 40,320, while for 21 paths it increases to 2.4329 x 1018 This proves the necessity of a more efficient method to find the optimal path. There are many problems associated with networks, out of which the following two are important 1. The travelling salesman problem (discussed earlier in section 4.10). 2. The minimal path problem. 5.10 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 shown in figure 5.8. Links work in both directions unless marked otherwise. The numbers on the links represent cost (in rupees) of going from one node to another. Find the route that involves the least cost