Изменения
Нет описания правки
#Для каждого ребра <tex>(u,v)</tex> данной сети <tex>G</tex> зададим <tex>f(u,v) = 0</tex>.
#Построим вспомогательную сеть <tex>G_L</tex> из [[Дополняющая сеть, дополняющий путь|дополняющей сети]] <tex>G_f</tex> данного графа <tex>G</tex>. Если <tex>d[t] = \infty</tex>, остановиться и вывести <tex>f</tex>.
#[[Алгоритм поиска блокирующего потока в ациклической сети|Найдем блокирующий поток <tex>f'</tex> в <tex>G_L</tex>.]].
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем к шагу 2.
}}
Поскольку длина кратчайшего <tex>s \leadsto t</tex> пути не может превосходить <tex>n - 1</tex>, то, следовательно, алгоритм Диница совершает не более <tex>n - 1</tex> фазы.
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь асимптотики <tex>O(VE\log V)</tex>, если использовать [[Link-Cut_Tree | динамические деревья Слетора и Тарьяна]].
==Реализация==
'''bool''' bfs():
заполняем массив d значениями, равными -1
Q.push(s)
'''while''' !Q.isEmpty
u = Q.pop()
'''for''' <tex>(uv) \in E(G)</tex>
'''if''' f[u][v] < c[u][v] and d[v] != -1
d[v] = d[u] + 1
Q.push(v)
'''return''' d[t] != -1
<font color="darkgreen">//поиск блокирующего потока
//v - номер вершины
//cf - минимальная пропускная способность дополняющей сети на пройденном dfs пути</font>
'''int''' dfs(u, cf):
'''if''' u == t '''or''' cf == 0
'''return''' cf
<font color="darkgreen">//p[u] - номер вершины на которой завершился обход для вершины u</font>
'''for''' v = p[u] '''to''' <tex>|V(G)| - 1</tex>
'''if''' d[v] == d[u] + 1 <font color="darkgreen">//это условие эквивалентно поиску во вспомогательной слоистой сети</font>
cfmin = dfs(v, min(cf, c[u][v] - f[u][v]))
f[u][v] += cfmin
f[v][u] -= cfmin
'''return''' cfmin
p[u]++
'''return''' 0
'''int''' findMaxFlow():
maxFlow = 0
'''while''' bfs() <font color="darkgreen">//пересчитываем d[i], заодно проверяем достижима ли t из s</font>
заполняем p нулями
flow = dfs(s, <tex>\infty</tex>)
'''while''' flow != 0
maxFlow += flow
flow = dfs(s, <tex>\infty</tex>)
'''return''' maxFlow
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
