NEW ALGORITHM FOR SOLUTION OF MAXIMUM FLOW PROBLEM
Abstract
A new algorithm for detection of a maximum flow in multi-terminal network. The algorithm is based on its matrices description and execution of ternary operations in respect of matrix elements pertaining to arc capacity. Therefore the algorithm does not require graphic network presentation. For this reason the programming realization of the developed algorithm is rather simple and it can be applied while solving a large scope of problems when mathematical models can be formulated in terms of a graph theory.
References
1. Floyd, R. W. Aigorithm 97: Shortest Path. Communication of ACM / R. W. Floyd – 1962. – № 5 (6). – 345 p.
2. Корзников, А. Д. Моделирование и оптимизация процесса перемещения грузов в логистической транспортной системе / А. Д. Корзников, В. А. Корзников // Вестник БНТУ. – 2003. – № 6. – С. 54–60.
3. Форд, Л. Р. Потоки в сетях / Л. Р. Форд, Д. Р. Фалкерсон. – М. : Мир, 1963. – 276 с.
4. Veinott, A. F. Integer Extrime Points / A. F. Veinot, Jr. and G. B. Dantzig // SIAM. Revjew. – 1968. – No 10 (3). – Р. 371–372.
Review
For citations:
Korznikov A.D. NEW ALGORITHM FOR SOLUTION OF MAXIMUM FLOW PROBLEM. Science & Technique. 2013;(5):70-75. (In Russ.)
Views: 1588
Email this article 