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

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

ОписаниеПравить

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

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

1. Если $(u,v)\in <!--\; \in \; -->E$$(u,v)\in E$ ,

   $c_f(u,v)=c(u,v)-<!--\; -\; -->f(u,v)$$c_{f}(u,v)=c(u,v)-f(u,v)$ 

   $c_f(v,u)=f(u,v)$$c_{f}(v,u)=f(u,v)$  В других источниках $c_f(u,v)=c(u,v)-<!--\; -\; -->f(u,v)+f(v,u)$$c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$ 

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

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

$E_f=\{(u,v)\in <!--\; \in \; -->V\times <!--\; \times \; -->V\mid <!--\; \mid \; -->c_f(u,v)>0\}$$E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\}$ .

Дополняющий путь — $s-<!--\; -\; -->t$$s-t$  путь в остаточном графе $G_f$$G_f$ .

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

$E_L=\{(u,v)\in <!--\; \in \; -->E_f\mid <!--\; \mid \; -->\mathrm{dist}<!--\; \; -->(v)=\mathrm{dist}<!--\; \; -->(u)+1\}$$E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\}$ .

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

АлгоритмПравить

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

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

Выход: $s-<!--\; -\; -->t$$s-t$  поток $f$$f$  максимальной величины.

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

АнализПравить

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

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

ПримерПравить

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

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

ИсторияПравить

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

Алгоритм Диница с распостранениемПравить

Временную сложность алгоритма можно уменьшить, если оптимизировать процесс поиска блокирующего потока. Для этого необходимо ввести понятие потенциала. Потенциал ребра $e\in <!--\; \in \; -->E$$e\in E$  есть $\mathrm{pot}<!--\; \; -->(e)=c_f(e)$$\operatorname {pot} (e)=c_{f}(e)$ , а потенциал вершины $v\in <!--\; \in \; -->V\setminus <!--\; \setminus \; -->\{s,t\}$$v\in V\setminus \{s,t\}$  равен $\mathrm{pot}<!--\; \; -->(v)=min\{\underset{e\in <!--\; \in \; -->{\mathrm{\delta <!--\; \delta \; -->}}^{+}(v)}{\sum <!--\; \sum \; -->}\mathrm{pot}<!--\; \; -->(e),\underset{e\in <!--\; \in \; -->{\mathrm{\delta <!--\; \delta \; -->}}^{-<!--\; -\; -->}(v)}{\sum <!--\; \sum \; -->}\mathrm{pot}<!--\; \; -->(e)\}$$\operatorname {pot} (v)=\min\{\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e),\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)\}$ . По той же логике $\mathrm{pot}<!--\; \; -->(s)=\underset{e\in <!--\; \in \; -->{\mathrm{\delta <!--\; \delta \; -->}}^{+}(v)}{\sum <!--\; \sum \; -->}\mathrm{pot}<!--\; \; -->(e)$$\operatorname {pot} (s)=\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e)$ , а $\mathrm{pot}<!--\; \; -->(t)=\underset{e\in <!--\; \in \; -->{\mathrm{\delta <!--\; \delta \; -->}}^{-<!--\; -\; -->}(v)}{\sum <!--\; \sum \; -->}\mathrm{pot}<!--\; \; -->(e)$$\operatorname {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)$  . Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди.

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

Выход: $s-<!--\; -\; -->t$$s-t$  поток $f$$f$  максимальной величины.

1. Установить $f(e)=0$$f(e)=0$  для каждого $e\in <!--\; \in \; -->E$$e\in E$ .
2. Создать $G_L$$G_L$  из $G_f$$G_f$  графа $G$$G$ . Если $\mathrm{dist}<!--\; \; -->(s,t)=\mathrm{\infty <!--\; \infty \; -->}$$\operatorname {dist} (s,t)=\infty$ , остановиться и вывести $f$$f$ .
3. Установить $f^{\prime }(e)=0$$f'(e)=0$  для каждого $e\in <!--\; \in \; -->E$$e\in E$ .
4. Определить потенциал каждой вершины.
5. Пока существует вершина $v\in <!--\; \in \; -->V$$v\in V$  такая, что $\mathrm{pot}<!--\; \; -->(v)>0$$\operatorname {pot} (v)>0$ :
   1. Определи поток $f^{″}$$f''$  при помощи прямого распостранения из $v$$v$ .
   2. Определи поток $f^{‴}$$f'''$  при помощи обратного распостранения из $v$$v$ .
   3. Дополни поток $f^{\prime }$$f'$  потоками $f^{″}$$f''$  и $f^{‴}$$f'''$ .
6. Дополнить поток $f$$f$  потоком $f^{\prime }$$f'$  и перейти к шагу 2.

Алгоритмы прямого и обратного распостранения служат поиску путей из $v$$v$  в $t$$t$  и из $s$$s$  в $v$$v$  соответственно. Пример работы алгоритма прямого распостранения с использованием очередей:

Вход: Вспомогательная сеть $G_L=(V,E_L,c_f{|}_{E_L},s,t)$$G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)$ , вершина $v\in <!--\; \in \; -->V$$v\in V$  такая, что $\mathrm{pot}<!--\; \; -->(v)>0$$\operatorname {pot} (v)>0$ .

Выход: Поток $f^{″}$$f''$  из источника $s$$s$  в вершину $v$$v$ , являющийся частью блокирующего потока.

1. Установить для всех $w\in <!--\; \in \; -->V\setminus <!--\; \setminus \; -->\{v\}$$w\in V\setminus \{v\}$ : $U(w)=0$$U(w)=0$ .
2. Установить $U(v)=\mathrm{pot}<!--\; \; -->(v)$$U(v)=\operatorname {pot} (v)$  и $\mathrm{pot}<!--\; \; -->(v)=0$$\operatorname {pot} (v)=0$ .
3. Добавить $v$$v$  в очередь $Q$$Q$ .
4. Пока очередь $Q$$Q$  не пуста:
   1. Установить значение $v$$v$  равным последнему элементу очереди.
   2. Пока $U(v)>0$$U(v)>0$ :
      1. Для каждого ребра $e=(v,w)\in <!--\; \in \; -->{\mathrm{\delta <!--\; \delta \; -->}}^{+}(v)$$e=(v,w)\in \delta ^{+}(v)$ :
      2. $f^{″}(e)=min\{\mathrm{pot}<!--\; \; -->(e),U(v)\}$$f''(e)=\min\{\operatorname {pot} (e),U(v)\}$ .
      3. Обнови $U(v)=U(v)-<!--\; -\; -->f^{″}(e)$$U(v)=U(v)-f''(e)$ .
      4. Обнови $U(w)=U(w)+f^{″}(e)$$U(w)=U(w)+f''(e)$ .
      5. Установи $\mathrm{pot}<!--\; \; -->(w)=\mathrm{pot}<!--\; \; -->(w)-<!--\; -\; -->\mathrm{pot}<!--\; \; -->(e)$$\operatorname {pot} (w)=\operatorname {pot} (w)-\operatorname {pot} (e)$ .
      6. Если $w\ne <!--\; \ne \; -->t$$w\neq t$  и $U(w)=f^{″}(e)$$U(w)=f''(e)$  удалить $w$$w$  из очереди $Q$$Q$ .

В связи с тем, что в каждой итерации поиска блокирующего потока "насыщается" минимум одна вершина, он завершается за $|V|-<!--\; -\; -->1$$|V|-1$  итераций в худшем случае, в каждой из которых рассматриваются максимум $|V|$$|V|$  вершин. Пусть $l_i$$l_{i}$  - количество "насыщенных" ребер в каждой $i$$i$ -той итерации поиска блокирующего потока. Тогда его асимптотическая сложность равна $\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}O(n+l_i)=O(n^2+\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{l}_i)=O(n^2+m)$$\sum _{i=1}^{n-1}O(n+l_{i})=O(n^{2}+\sum _{i=1}^{n-1}l_{i})=O(n^{2}+m)$ , где $n$$n$  - количество вершин и $m$$m$  - количество ребер в графе. Таким образом, асимптотическая сложность алгоритма Диница с распостранением равна $O(|V{|}^3)$$O(|V|^{3})$ , так как блокирующий поток может проходить максимум через $|V|$$|V|$  вершин.

ЛитератураПравить

• 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++