10. Пусть Т - ориентированный остов графа G = {X, А) и корнем остова Т является вершина s. Пусть I (х;) - расстояние от вершины S до вершины х измеренное вдоль пути в этом дереве. Показать, что Т является s-базой тогда и только тогда, когда для каждой дуги (xi, Xj) 6 А выполняется условие I (xj)l (Xi) + Ctj.

И. Теорема из задачи 10 является основой следуюш;ей итерационной процедуры нахождения кратчайшего пути от s ко всем другим вершинам графа (здесь мы предполагаем, что все вершины Xi 6 X достижимы из s).

Шаг 1. Взять в качестве Т любой ориентированный остов графа G и для каждой вершины х, найти пометку I (х,-), равную расстоянию между этой вершиной и корнем s вдоль пути в дереве Т.

Шаг 2. Если каждая дуга (х^, xj) 6 А удовлетворяет условию

l{Xj)l(Xi)+Cij,

то остановиться. Текущий остов Т будет s-базой графа G. В противном случае перейти к шагу 3.

Шаг 3. Если для некоторой дуги (хь xj)

Hxi)>Hxi)+Cij-,

то добавить к дереву дугу (х Xj) и удалить из него ту дугу (х, Xj), конечной вершиной которой является Xj, после чего возникает новое дерево Т.

Шаг 4. Обновить пометки I (х^) у всех вершин х^, достижимых из Xj вдоль путей дерева Т. Возвратиться к шагу 2.

Показать, что вышеописанный алгоритм является конечным, и показать, что его сложность для полного ге-вершинного графа растет как О (и^). Налагает ли алгоритм какие-либо ограничения на веса Cj? Используя этот алгоритм, проверить решение задачи 2 (см. [14]).

9. Список литературы

1. Balas Е. (1969), Project scheduling with resources constraints, IBM New York Scientific Center, Report No. 320-2960.

2. Bellman R. (1958), On a routing problem. Quart, of Applied Mathematics, 16, p. 87.

3. Bellman R., Kalaba R. (1960), On k-best policies, /. of SIAM, 8, p. 582.

4. Berry R. C. (1971), A constrained shortest path algorithm. Paper presented at the 39th National ORSA Meeting, Dallas, Texas.

5. Brucker P. (1972), All shortest distances in networks with a large number of strong components. Presented at the 41st National Meeting Research Soc. of America, New Orleans.

6. Cunninghame-Green R. A. (1962), Describing industrial processes with interference and approximating their steady-state behaviour, Opl. Res. Quart., 13, p. 95.

7. Dantzig G. B. (1966), All shortest routes in a graph. Int. Symp. on Theory of Graphs, Dunod, Paris, p. 91.

8. Dantzig G. В., Blattner W. 0., Rao M. R. (1966), All shortest routes from a fixed origin in a graph. Int. Symp. on Theory of Graphs, Dunod, Paris, p. 85.

9. Dantzig G. В., Blattner W. 0., Rao M. R. (1966), Finding a cycle in a graph with minimum cost to time ratio with applications to a ship routing problem. Int. Symp. on Theory of Graphs, Dunod, Paris, p. 77.

to. Dijkstra E. W. (1959), A note on two problems in connection with graphs, Numerische Mathematik, 1, p. 269.

11. Dreyfus S. E. (1969), An appraisal of some shortest path algorithms. Ops. Res., 17, p. 395.

12. Ermolev Yu. M. (1966), Shortest admissible paths I, Kibernetika, 2, p. 88.

13. Floyd R. W. (1962), Algorithm 97 - Shortest path. Comm. of ACM, 5, p. 345.

14. Ford L. R. Jr. (1946), Network flow theory. Rand Corporation Report P-923.

15. Fox B. (1969), Finding a minimal cost to time ratio circuit. Ops. Res., 17, p. 546.

16. Frank H., Frisch I. T. (1971), Communication, Transmission and Transportation Networks, Addison-Wesley, Reading, Massachusetts.

17. Gill A., Traiger T. (1968), Computation of optimal paths in finite graphs, Proc. 2nd Int. Conf. on Сотр. Methods in Optimization Problems, San Remo, Italy.

18. Kitchener L. E. (1968), A comparative investigation of the computational efficiency of shortest path algorithms. Operations Research Centre, University of California, Berkeley, Report ORC 68-17.

19. Hoffman A. J., Winograd S. (1971), On finding all shortest distance in a directed network, IBM, Thomas J. Watson Research Center, Report RC 3613.

20. Hoffman W., Pavley R. (1959), A method for the solution of the N best path problem, /. of ACM, 6, p. 506.

21. Hu T. C. (1969), Integer programming and network flows, Addison-Wesley, Reading, Massachusetts.

22. Johnson E. L. (1972), On shortest paths and sorting, Proc. of Annual Conf. of ACM, Boston, p. 510.

23. Joksch H. C. (1966), The shortest route problem with constraints, /. of Math. Anal, and Appl., 14, p. 191.

24. Lawler E. L. (1966), Optimal cycles in doubly weighted directed linear graphs. Int. Symp. on Theory of Graphs, Dunod, Paris, p. 209.

25. Minieka E. (1971), All fe-shortest paths in a graph. Internal Report, Department of Statistics, Trinity College, Dublin.

26. Moore E. F. (1957), The shortest path through a maze, Proc. Int. Symp. on the Theory of Switching, Part II, p. 285.

27. Murchland J. D. (1965), A new method for finding all elementary paths in a complete directed graph, London School of Economics, Report LSE-TNT-22.

28. Murchland J. D. (1967), The once-through method of finding all shortest distances in a graph from a single origin, London Graduate School of Business Studies, Report LBS-TNT-56.

29. Nicholson T. A. J. (1966), Finding the shortest route between two points in a network. The Computer J., 9, p. 275.

30. Raimond J. F. (1969), Minimaximal paths in disjunctive graphs by direct search, IBM J. of Res. and Dev., 13, p. 391.

216 гл. 8. кратчайшие пути

31. Rciter R. (1968), Scheduling parallel computation, /. о/ ACM. 15, p. 590. ?2, Sakarovitch M. (1966), The ft-shortest routes and Л-shortest chains in a

graph. Operations Research Centre, University of California, Berkeley,

Report ORG 66-32.

3. Shapiro J. F. (1968), Shortest route method for finite state space dynamic programming problems, /. of SIAM {Appl. Maths,), 16, p. 1232.

34, Taha H. A. (1971), Operations Research, Macmillan, New York.

35. Yen J. Y. (1971), Finding ,the fc-shortest, loopless paths in a network, Man. Sci., 17, p. 712.

SO. Yen J. Y. (1971), On thefefficiencies of algorithms for detecting negative loops in networks, Santa Clara Business Review, p. 52.

с7. Zaioom V. (1971), On the resource-constrained project sheduling problem, AIIE Trans., 3, p. 302.