Схема алгоритма Диница

Определение слоистой сети

Для начала определим для каждой вершины [math]v[/math] данной сети [math]G[/math] длину кратчайшего [math]s \leadsto v[/math] пути из истока и обозначим ее [math]d[v][/math] (для этого можно воспользоваться обходом в ширину).

В слоистую сеть включаем только те ребра [math](u,v)[/math] исходной сети, для которых [math]d[u] + 1 = d[v][/math]. Полученная сеть ациклична, и любой [math]s \leadsto t[/math] путь в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.

Слоистая сеть с пятью слоями. [math]s = 0, t = 6[/math]

В примере ребра, обозначенные пунктиром, не входят в слоистую сеть.

Слоистую сеть для графа G будем называть вспомогательной сетью.

Алгоритм

Пусть дана сеть. Требуется найти в этой сети поток [math]f(u,v)[/math] из [math]s[/math] в [math]t[/math] максимальной величины.

Схема алгоритма

1. Для каждого ребра [math](u,v)[/math] данной сети [math]G[/math] зададим [math]f(u,v) = 0[/math].
2. Построим вспомогательную сеть [math]G_L[/math] из дополняющей сети [math]G_f[/math] данного графа [math]G[/math]. Если [math]d[t] = \infty[/math], остановиться и вывести [math]f[/math].
3. Найдем блокирующий поток [math]f'[/math] в [math]G_L[/math].
4. Дополним поток [math]f[/math] найденным потоком [math]f'[/math] и перейдем к шагу 2.

Корректность алгоритма

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

В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим во вспомогательной сети из истока. Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя теорему Форда-Фалкерсона, получаем, что текущий поток в самом деле максимален.

Асимптотика алгоритма

Теорема:

Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. [math]d'[t] \gt d[t][/math], где [math]d'[t][/math] — значение, полученное на следующей фазе алгоритма.

Доказательство:

[math]\triangleright[/math]

Проведём доказательство от противного. Пусть длина кратчайшего пути из истока в сток останется неизменной после очередной фазы алгоритма. Вспомогательная сеть строится по остаточной. Из предположения следует, что в остаточной сети будет содержаться только рёбра остаточной сети перед выполнением данной фазы, либо обратные к ним. Из этого получаем, что нашёлся [math]s \leadsto t[/math] путь, который не содержит насыщенных рёбер и имеет ту же длину, что и кратчайший путь. Но этот путь должен был быть «заблокирован» блокирующим потоком, чего не произошло. Получили противоречие. Значит длина изменилась.

[math]\triangleleft[/math]

Поскольку длина кратчайшего [math]s \leadsto t[/math] пути не может превосходить [math]n - 1[/math], то, следовательно, алгоритм Диница совершает не более [math]n - 1[/math] фазы. Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за [math]O(VE^2)[/math] или за [math]O(V^2E)[/math]. Также возможно достичь асимптотики [math]O(VE\log V)[/math], если использовать динамические деревья Слетора и Тарьяна.

Реализация

В данной реализации не строится вспомогательная сеть [math]G_L[/math], а вычисляются значения [math]d[u][/math] — кратчайших путей [math]s \leadsto u[/math].

[math]c[u][v][/math] — пропускная способность ребра [math](uv)[/math].

[math]f[u][v][/math] — поток через ребро [math](uv)[/math].

[math]p[u][/math] — номер первого неудаленного ребра идущего из u

bool bfs():
  заполняем массив d значениями, равными [math]\infty[/math]
  d[s] = 0
  Q.push(s)
  while !Q.isEmpty
    u = Q.pop()
    for [math](uv) \in E(G)[/math]
      if f[u][v] < c[u][v] and d[v] == [math]\infty[/math]
        d[v] = d[u] + 1
        Q.push(v)
  return d[t] != [math]\infty[/math]

// поиск блокирующего потока
// u — номер вершины
// minC — минимальная пропускная способность дополняющей сети на пройденном dfs пути
int dfs(u, minC):
  if u == t or minC == 0
    return minC
  for v = p[u] to [math]|V(G)| - 1[/math]
    if d[v] == d[u] + 1 // это условие эквивалентно поиску во вспомогательной слоистой сети
      delta = dfs(v, min(minC, c[u][v] - f[u][v]))
      if delta != 0
        f[u][v] += delta // насыщаем ребра по пути dfs
        f[v][u] -= delta
        return delta
    p[u]++
  return 0

int findMaxFlow():
  maxFlow = 0
  while bfs() // пересчитываем d[i], заодно проверяем достижима ли t из s
    заполняем p нулями
    flow = dfs(s, [math]\infty[/math])
    while flow != 0
      maxFlow += flow
      flow = dfs(s, [math]\infty[/math])
  return maxFlow

Источники

• Википедия — Алгоритм Диница
• MAXimal::algo::Алгоритм Диница
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4