Как применить алгоритм Форда-Фалкерсона к графу, чтобы найти максимальный поток в потоковой сети?

Может кто-нибудь направить меня на сайт, где даны пошаговые инструкции о том, как применить метод Форда-Фулкерсона на графике, чтобы найти максимальный поток.

Огромное спасибо заранее.


algorithm max-flow ford-fulkerson
person sap    schedule 03.11.2010    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Насколько мне известно ( ссылка ), википедия ( ссылка ) и первый альтернативный поиск Google ( Ссылка ).

Алгоритм маркировки Форда-Фалкерсона

  • (Инициализация) Пусть x будет начальным допустимым потоком (например, x(e) = 0 для всех e в E).
  • (Flow augmentation) If there are no augmenting path from s to t on the residual network, then stop. The present x is a max flow. If there is a flow augmenting path p, replace the flow x as 2.
    • x(e)=x(e)+delta if e is a forward arc on p.
    • x(e)=x(e)-дельта, если e — обратная дуга на p. где дельта – минимальное значение остаточной емкости на с. Повторите этот шаг.

Пример исходного кода: Java< /а>

person Margus    schedule 03.11.2010
comment
Спасибо за вашу помощь. нашел это фантастическое объяснение: topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow - person sap; 04.11.2010

arrow_upward
0
arrow_downward

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

person l337x911    schedule 03.11.2010
comment
Я просмотрел статью в Википедии, это не имело никакого смысла. - person sap; 03.11.2010

arrow_upward
0
arrow_downward

также интересна теорема о минимальном разрезе. максимальное количество потока, проходящего от истока к стоку, равно минимальному разрезу ребер и их расходу. я просто завалил этот вопрос в школе :(

http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

person ColacX    schedule 06.03.2013