double arrow

Алгоритм Форда-Фалкерсона (отыскания max потока)

1. Пусть j (l)>0, " l Î А; m0 (l)=0; k =1.

2. Находим произвольный ориентированный путь из S/ в S// в графе G=(Vk,Ak,jk) и строим mk: А® R+ по следующему правилу.

Выбираем число и строим поток, пропущенный на данной итерации по дугам выбранного пути:

После чего пересчитываем оставшиеся пропускные способности дуг:

3. Дуги, для которых jк+1 ( )=Æ, удаляются из Gк+1 =(V,Ak+1,jk+1).

4. Если на шаге k в графе G нельзя найти ориентированный путь из S/ в S//, то остановка. Таким образом, mк ( )- искомый поток, а

Иначе, переходим к шагу 2.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: