![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм построения максимального потока в транспортной сети ⇐ ПредыдущаяСтр 2 из 2
Алгоритм состоит в последовательном просмотре вершин сети и присвоении им отметок. На каждом шаге алгоритма любая вершина находится в одном из трех состояний: а) не помечена; б) помечена, но не просмотрена; в) помечена и просмотрена. 0-й шаг. Зададим какой-нибудь, например, нулевой поток по сети. 1-й шаг. Помети источник 2-й шаг. Берем очередную помеченную, но не просмотренную вершину а) дуга выходит из вершины б) дуга входит в вершину После завершения этого шага вершина Шаг 2 циклически повторяется до тех пор, пока не произойдет одно из двух событий, рассматриваемых далее на 3-ем и 4-ом шагах. 3-й шаг. Сток 4-й шаг. Процесс расстановки отметок закончился тем, что все помеченные вершины просмотрены, но сток Пример 2. Пусть задана транспортная сеть и поток по ней (рис. 2).
10, 7 4, 4 5, 5
5, 5 6, 2
3, 3 Рис. 2. Процесс расстановки отметок показан в таблице 1. Таблица 1
Поскольку сток получил отметку, то строим прибавляющую цепь (рис. 3).
Рис. 3.
Увеличиваем поток на две единицы на прямых дугах этой цепи и уменьшаем на две единицы на обратных. В результате получаем поток, изображенный на рис. 4.
10, 9 4, 4 5, 5
5, 5 6, 4
3, 3 Рис. 4. В процессе расстановки отметок для нового потока удается пометить только вершины совпадает с величиной потока или
|