А л г о р и т м
Построения максимального потока
Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг. Результат: максимальный поток в сети. 1. Полагаем i = 0. Пусть j0 – любой допустимый поток в транспортной сети D (например, полный или нулевой). 2. По сети D и потоку ji строим орграф приращений I(D, ji). 3. Находим простую цепь mi, являющуюся минимальным путем из v1 в vn в нагруженном орграфе I(D, ji) (можно использовать любой описанный выше алгоритм). Если длина этой цепи равна ¥, то поток ji максимален и работа алгоритма заканчивается. В противном случае увеличиваем поток вдоль цепи mi на максимально допустимую величину ai > 0, где aiÎZ (прибавляя ее для каждой дуги xÎX, через которую проходит цепь mi, к уже имеющейся величине потока по дуге x, если дуга x входит в mi, и вычитая, если дуга x* входит в mi), такую, что при этом сохраняется условие допустимого потока. В результате меняется поток в транспортной сети D, т.е. от потока ji переходим к потоку ji+1, который является допустимым, и при этом величина его увеличивается на ai. Присваиваем i = i + 1 и переходим к шагу 2.
Алгоритм меток для нахождения максимального потока Рассмотрим другой алгоритм построения максимального потока в транспортной сети, использующий метки вершин.
Помечивающий алгоритм Форда – Фалкерсона
|
