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.







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