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

Материал из Википедии — свободной энциклопедии

Черновик [показать страницу] (сравнить)

Данная версия статьи не досматривалась участниками с соответствующими правами. Вы можете прочитать последнюю досмотренную версию от 19 сентября 2008, однако она может значительно отличаться от текущей версии. Проверки требуют 22 правки.

Перейти к: навигация, поиск

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: $f (u, v) = 0$ для всех $u,v \in V$ . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

[править] Алгоритм

Дан граф $G (V, E)$ с пропускной способностью $c (u, v)$ и потоком $f (u, v) = 0$ для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

$\ f(u,v) \leqslant c(u,v)$ . Поток из $u$ в $v$ не превосходит пропускной способности.
$\ f(u,v) = - f(v,u)$ .
$\ \sum_v f(u,v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u)$ для всех узлов $u$ , кроме $s$ и $t$ . Поток не изменяется при прохождении через узел.

Остаточная сеть $G f (V, E f)$ — сеть с пропускной способностью $c f (u, v) = c (u, v) - f (u, v)$ и без потока.

Вход Граф $\,G$ с пропускной способностью $\,c$ , источник $\,s$ и сток $\,t$
Выход Максимальный поток $\,f$ из $\,s$ в $\,t$

$f(u,v) \leftarrow 0$ для всех ребер $\,(u,v)$
Пока есть путь из в в , такой что для всех ребер :
1. Найти $\,c_f(p) = \min\{c_f(u,v) \;|\; (u,v) \in p\}$
2. Для каждого ребра
  1. $f(u,v) \leftarrow f(u,v) + c_f(p)$
  2. $f(v,u) \leftarrow f(v,u) - c_f(p)$

Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса-Карпа) или поиском в глубину в $G f (V, E f)$ .

[править] Сложность

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено O(E*f), где E — число вершин в графе, f — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за O(E) и увеличивает поток как минимум на 1.

[править] Пример

Следующий пример показывает первые шаги алгоритма Форда-Фалкерсона в транспортной сети с четырьмя узлами, источником A и стоком D. Этот пример показывает худший случай. При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.

Путь	Пропускная способность	Результат
	Начальная транспортная сеть
$A, B, C, D$	$min(c f (A, B), c f (B, C), c f (C, D)) =$ $min(c (A, B) - f (A, B), c (B, C) - f (B, C), c (C, D) - f (C, D)) =$ $min(1000 - 0,1 - 0,1000 - 0) = 1$
$A, C, B, D$	$min(c f (A, C), c f (C, B), c f (B, D)) =$ $min(c (A, C) - f (A, C), c (C, B) - f (C, B), c (B, D) - f (B, D)) =$ $min(1000 - 0,0 - ( - 1),1000 - 0) = 1$
	После 1998 шагов …
	Конечная сеть

[править] Cсылки

[править] Литература

Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

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

Материал из Википедии — свободной энциклопедии

Содержание

[править] Алгоритм

[править] Сложность

[править] Пример

[править] Cсылки

[править] Литература

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

На других языках