WikiSort.ru - Не сортированное

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

Описание

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

Остаточная пропускная способность — отображение ${\displaystyle c_{f}\colon V\times V\to R^{+}}$ определённое как:

1. Если ${\displaystyle (u,v)\in E}$ ,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

   ${\displaystyle c_{f}(v,u)=f(u,v)}$

2. ${\displaystyle c_{f}(u,v)=0}$ иначе.

Остаточная сеть — граф ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$ , где

${\displaystyle E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\}}$ .

Дополняющий путь — ${\displaystyle s-t}$ путь в остаточном графе ${\displaystyle G_{f}}$ .

Пусть ${\displaystyle \operatorname {dist} (v)}$  — длина кратчайшего пути из ${\displaystyle s}$ в ${\displaystyle v}$ в графе ${\displaystyle G_{f}}$ . Тогда вспомогательная сеть графа ${\displaystyle G_{f}}$  — граф ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$ , где

${\displaystyle E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$ .

Блокирующий поток — ${\displaystyle s-t}$ поток ${\displaystyle f}$ такой, что граф ${\displaystyle G'=(V,E_{L}',s,t)}$ с ${\displaystyle E_{L}'=\{(u,v)\mid f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ не содержит ${\displaystyle s-t}$ пути.

Алгоритм

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

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

Выход: ${\displaystyle s-t}$ поток ${\displaystyle f}$ максимальной величины.

1. Установить ${\displaystyle f(e)=0}$ для каждого ${\displaystyle e\in E}$ .
2. Создать ${\displaystyle G_{L}}$ из ${\displaystyle G_{f}}$ графа ${\displaystyle G}$ . Если ${\displaystyle \operatorname {dist} (t)=\infty }$ , остановиться и вывести ${\displaystyle f}$ .
3. Найти блокирующий поток ${\displaystyle f\;'}$ в ${\displaystyle G_{L}}$ .
4. Дополнить поток ${\displaystyle \ f}$ потоком ${\displaystyle f\;'}$ и перейти к шагу 2.

Анализ

Можно показать, что каждый раз число рёбер кратчайшем пути из источника в сток увеличивается хотя бы на единицу, поэтому в алгоритме не более ${\displaystyle n-1}$ блокирующих потоков, где ${\displaystyle n}$  — число вершин в сети. Вспомогательная сеть ${\displaystyle G_{L}}$ может быть построена обходом в ширину за время ${\displaystyle O(E)}$ , а блокирующий поток на каждом уровне графа может быть найден за время ${\displaystyle O(VE)}$ . Поэтому время работы алгоритма Диница есть ${\displaystyle O(V)\cdot (O(E)+O(VE))=O(V^{2}E)}$ .

Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время ${\displaystyle O(E\log V)}$ , тогда время работы алгоритма Диница может быть улучшено до ${\displaystyle O(VE\log V)}$ .

Пример

Ниже приведена симуляция алгоритма Диница. Во вспомогательной сети ${\displaystyle G_{L}}$ вершины с красными метками — значения ${\displaystyle \operatorname {dist} (v)}$ . Блокирующий поток помечен синим.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	Блокирующий поток состоит из путей: ${\displaystyle \{s,1,3,t\}}$ с 4 единицами потока, ${\displaystyle \{s,1,4,t\}}$ с 6 единицами потока, и ${\displaystyle \{s,2,4,t\}}$ с 4 единицами потока. Следовательно, блокирующий поток содержит 14 единиц, а величина потока ${\displaystyle |f|}$ равна 14. Заметим, что дополняющий путь имеет 3 ребра.
2.
	Блокирующий поток состоит из путей: ${\displaystyle \{s,2,4,3,t\}}$ с 5 единицами потока. Следовательно, блокирующий поток содержит 5 единиц, а величина потока ${\displaystyle |f|}$ равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.
3.
	Сток ${\displaystyle t}$ не достижим в сети ${\displaystyle G_{f}}$ . Поэтому алгоритм останавливается и возвращает максимальный поток величины 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.

Ссылки

• Алгоритм Диница на сайте e-maxx.ru: Описание, доказательства, реализация на C++