Алгоритм Диница

Алгоритм Диница, полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году израильским (бывшим русским) учёным Ефимом Диницем. Временная сложность алгоритма составляет O(V2E). Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: O(EV).

Пусть G = ((V,E),c,s,t) — сеть, в которой c(u,v) и f(u,v) — соответственно пропускная способность и поток через ребро (u,v).

Остаточная пропускная способность — отображение  определённое как:

1. Если ,

   cf(u,v) = c(u,v) − f(u,v)

   cf(v,u) = f(u,v)

2. cf(u,v) = 0 иначе.

Остаточная сеть — граф , где

.

Дополняющий путь — s − t путь в остаточном графе Gf.

Пусть  — длина кратчайшего пути из s в v в графе Gf. Тогда вспомогательная сеть графа Gf — граф , где

.

Блокирующий поток — s − t поток f такой, что граф G' = (V,EL',s,t) с  не содержит s − t пути.

Алгоритм:

Алгоритм Диница

Вход: Сеть G = ((V,E),c,s,t).

Выход: s − t поток f максимальной величины.

1. Установить f(e) = 0 для каждого .

2. Создать GL из Gf графа G. Если , остановиться и вывести f.

3. Найти блокирующий поток  в GL.

4. Дополнить поток  потоком  и перейти к шагу 2. 

Можно показать, что каждый раз количество рёбер в блокирующем потоке увеличивается хотя бы на одно, поэтому в алгоритме не более n − 1 блокирующих потоков, где n — количество вершин в сети. Вспомогательная сеть GL может быть построена обходом в ширину за время O(E), а блокирующий поток на каждом уровне графа может быть найден за время O(VE). Поэтому время работы А.Д. есть O(V2E).

Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время O(Elog V), тогда время работы А.Д. может быть улучшено до O(VElogV).

Ниже приведена симуляция А.Д. Во вспомогательной сети GL вершины с красными метками — значения . Блокирующий поток помечен синим.

	G	Gf	GL
1.
	Блокирующий поток состоит из путей: {s,1,3,t} с 4 единицами потока, {s,1,4,t} с 6 единицами потока, и {s,2,4,t} с 4 единицами потока. Следовательно, блокирующий поток содержит 14 единиц, а величина потока | f | равна 14. Заметим, что дополняющий путь имеет 3 ребра.
2.
	Блокирующий поток состоит из путей: {s,2,4,3,t} с 5 единицами потока. Следовательно, блокирующий поток содержит 5 единиц, а величина потока | f | равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.
3.
	Сток t не достижим в сети Gf. Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно.

А.Д. был опубликован в 1970 г. бывшим русским учёным Ефимом Диницем, который сейчас является членом факультета вычислительной техники университета Бен-Гурион (Израиль), ранее, чем алгоритм Эдмондса — Карпа, который был опубликован в 1972, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.

Лит.:  Yefim Dinitz Dinitz' Algorithm: The Original Version and Even's Version // Theoretical Computer Science: Essays in Memory of Shimon Even / Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman — Springer, 2006. — P. 218–240. — ISBN 978-3540328803. B. H. Korte, Jens Vygen 8.4 Blocking Flows and Fujishige's Algorithm // Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21) — Springer Berlin Heidelberg, 2008. — P. 174–176. — ISBN 978-3-540-71844-4.