2015-08-21
302
3.4.1 Study sub item 2.1, 2.3.5, 2.3.6 of the Key statements.
3.4.2 Build routing matrixes for each network knot (n =10) providing main route selecting and also two bypaths while connecting sections setting up from the considered knot to all the others.
For a main route (a way of the first sampling) it is necessary to use the shortest paths from the knot s (s =1.... n) to other network points. For bypaths (paths of the second and third selections) - the shortest paths by transits at maximum admissible transience Т 0 = 2. In the presence of several paths of equal transience preference one should favor to the shortest by length path.
For definition of the shortest by length paths as initial matrix of lengths of the lines connecting knot network points, take advantage of the weight matrix obtained while performing the Task 3.1 and for minimum transience path finding - contiguity matrixes.
3.4.3 Methodical instructions.
Routing matrixes are stored in every UК i networks and intended for definition of a direction of the proceeding communication line (communication channel) at connecting section of information message transmitting from initial point to the point of destination. It is possible to forsee additional directions (bypaths) selection in case of the first selection of occupation direction on the definite UК s in the presence of the switching equipment feasibilities. The order of directions selecting is defined by a routing matrix the quantity and line-numbering of which match to paths number p and to the assigned order of their occupation, and columns number - to points of destination numbers (figure 3.1).
| … | j | i | … | n | |||
| j | I | ||||||
| r | J |
… … … … … … … … … … … … … … … … … … ….
| p | l | L |
Figure 3.1
Element m ij of routing matrix for UК s is the knot number of contiguous UК s in transit of matching selection from UК s to the point of destination J.
3.4.4 Show the general problem assignment (verbal model), results of the solution and explanations matching to them in the explanatory note.
3.4.5 Answer the following key questions in writing:
- What class of problems does routing matrixes construction refer to?
- What is called the path in a network, a path length, way transience and the shortest way?
- Show practical situations where there is a problem of the shortest way definition.
- What is Dijkstra's algorithm of the shortest ways searching based on?
- What kinds of mark are used at Dijkstra's algorithm operation?
- Is it possible by means of Dijkstra's algorithm to find paths variety, the shortest by transience? Which initial data are required for this purpose?
- What method is it possible to obtain paths variety of set transience by?
- What does the idea of multilevel tree construction method consist in?
