Привет, будущие инженеры и программисты! Сегодня мы погрузимся в мир алгоритмов и разберём одну очень крутую штуку — алгоритм Диница. Звучит сложно? Не переживайте, мы разберём его по полочкам, как конструктор LEGO, и вы поймёте, как он помогает решать реальные задачи.

Представьте, что у вас есть город, и по его дорогам едут машины. У каждой дороги есть своя пропускная способность — сколько машин может проехать по ней за час. Ваша задача — понять, сколько всего машин может проехать из одной точки города (например, от завода) в другую (например, до торгового центра) за час, используя все дороги. Это и есть задача о максимальном потоке!

Такие задачи встречаются не только в дорогах. Это может быть:

• Водопровод: сколько воды можно прокачать из водохранилища в город?

• Интернет: сколько данных можно передать от сервера к пользователю?

• Производство: сколько продукции можно произвести и доставить?

Алгоритм Диница — это один из самых эффективных способов решить эту задачу. Он был придуман советским математиком Ефимом Диницем в 1970 году.

1. Основные понятия: Что такое "сеть" и "поток"?

Чтобы понять алгоритм, давайте сначала разберёмся с терминами:

• Граф (или сеть): Это как карта города. На ней есть:

  • Вершины (или узлы): Это точки на карте — перекрёстки, здания, города. В нашем коде они будут просто числами: 0, 1, 2 и так далее.

  • Рёбра (или связи): Это дороги, трубы, провода, соединяющие вершины. Каждое ребро идёт от одной вершины к другой (например, дорога с односторонним движением).

• Исток (Source, s): Это начальная точка, откуда "выходит" поток (например, завод, водохранилище).

• Сток (Sink, t): Это конечная точка, куда "приходит" поток (например, торговый центр, город).

• Пропускная способность (Capacity, Cap): Это максимальное количество "потока", которое может пройти через одно ребро. Например, по дороге может проехать 10 машин в час.

• Поток (Flow): Это то количество "потока", которое реально проходит через ребро в данный момент. Оно всегда должно быть меньше или равно пропускной способности.

2. Идея алгоритма Диница: "Уровни" и "блокировка"

Представьте, что вы хотите отправить как можно больше машин из точки А в точку Б. Вы не просто ищете один путь и отправляете по нему машины. Диниц делает это умнее:

1. Строим "уровни" (Level Graph): Сначала алгоритм смотрит на всю сеть и определяет, насколько "далеко" каждая вершина находится от истока. Это как если бы вы присвоили каждому перекрёстку номер: "0" для истока, "1" для перекрёстков, до которых можно доехать за 1 шаг от истока, "2" — за 2 шага и так далее. Это делается с помощью поиска в ширину (BFS). Мы будем отправлять поток только по рёбрам, которые ведут "вперёд" по этим уровням (например, с уровня 0 на уровень 1, с 1 на 2 и т.д.). Это помогает избежать "круговых" движений и быстрее найти путь.  

2. Ищем "блокирующий поток" (Blocking Flow): После того как уровни построены, алгоритм пытается "протолкнуть" как можно больше потока из истока в сток, двигаясь строго по этим уровням. Он ищет пути с помощью поиска в глубину (DFS) и отправляет по ним поток. Если на каком-то пути пропускная способность заканчивается, этот путь "блокируется". Алгоритм продолжает искать другие пути по уровням, пока не сможет протолкнуть больше ни одной единицы потока по текущему набору уровней. Этот максимальный поток, который можно отправить по текущему уровневому графу, называется блокирующим потоком.  

3. Повторяем: После того как блокирующий поток найден и отправлен, сеть меняется (пропускные способности рёбер уменьшаются). Алгоритм снова строит новые уровни (потому что старые пути могли быть заблокированы) и снова ищет блокирующий поток. Он повторяет эти шаги, пока из истока в сток больше нельзя будет отправить ни одной единицы потока.  

В итоге, сумма всех найденных блокирующих потоков и будет максимальным потоком в сети!

3. Остаточный граф и обратные рёбра: "Отменить" движение

Один из ключевых моментов в алгоритме Диница (и в других алгоритмах максимального потока, таких как Форда-Фулкерсона) — это концепция остаточного графа и обратных рёбер.

Представьте, что вы отправили 5 машин по дороге из А в Б. Но потом вы поняли, что было бы эффективнее отправить 3 машины по другой дороге, а по этой — только 2. Как это сделать? В реальной жизни машины не могут "поехать назад" по односторонней дороге. Но в алгоритме мы можем "отменить" часть потока.

Для этого, когда мы добавляем ребро из u в v с пропускной способностью C, мы также неявно добавляем обратное ребро из v в u с пропускной способностью 0.  

Когда мы отправляем поток f по прямому ребру u → v:

• Пропускная способность прямого ребра u → v уменьшается на f.

• Пропускная способность обратного ребра v → u увеличивается на f.

Зачем это нужно? Если позже алгоритм найдёт более эффективный путь, который использует обратное ребро v → u, это будет означать, что часть потока, который мы изначально отправили по u → v, как бы "отменяется" и перенаправляется. Это позволяет алгоритму "передумывать" и находить оптимальное решение, даже если первые шаги были не самыми лучшими.

4. Пример работы алгоритма Диница

Давайте рассмотрим простой пример, который есть в нашем коде. У нас есть 4 вершины (0, 1, 2, 3) и следующие дороги (рёбра) с их пропускными способностями:

• 0 → 1 (3 машины)

• 0 → 2 (2 машины)

• 1 → 2 (5 машин)

• 1 → 3 (2 машины)

• 2 → 3 (3 машины)

Исток s = 0, сток t = 3.

Итерация 1:

1. BFS (Строим уровни от истока 0):

   • level = 0 (исток)

   • Из 0 можно попасть в 1 и 2. Значит:

     • level[1] = 1

     • level[2] = 1

   • Из 1 можно попасть в 2 (но level[2] уже 1, и мы не идём назад по уровням) и в 3. Значит:

     • level[3] = 2

   • Из 2 можно попасть в 3. Значит:

     • level[3] остаётся 2.

   • Сток 3 достижим (level[3] = 2), продолжаем.

   Уровни: 0:0, 1:1, 2:1, 3:2.

2. DFS (Ищем блокирующий поток):

   • Начинаем из 0.

   • Путь 0 → 1 (ёмкость 3). Идём дальше из 1.

   • Путь 1 → 3 (ёмкость 2). Дошли до стока 3!

   • Минимальная ёмкость на пути 0 → 1 → 3 это min(3, 2) = 2. Отправляем 2 единицы потока.

     • Ёмкость 0 → 1 становится 3 - 2 = 1.

     • Ёмкость 1 → 3 становится 2 - 2 = 0.

     • Ёмкость обратного 1 → 0 увеличивается на 2.

     • Ёмкость обратного 3 → 1 увеличивается на 2.

   • Возвращаемся в 0. Пытаемся найти ещё путь.

   • Путь 0 → 2 (ёмкость 2). Идём дальше из 2.

   • Путь 2 → 3 (ёмкость 3). Дошли до стока 3!

   • Минимальная ёмкость на пути 0 → 2 → 3 это min(2, 3) = 2. Отправляем 2 единицы потока.

     • Ёмкость 0 → 2 становится 2 - 2 = 0.

     • Ёмкость 2 → 3 становится 3 - 2 = 1.

     • Ёмкость обратного 2 → 0 увеличивается на 2.

     • Ёмкость обратного 3 → 2 увеличивается на 2.

   • Из 0 больше нет путей по уровням. Блокирующий поток для этой итерации: 2 + 2 = 4.

   • Общий поток = 4.

Итерация 2:

1. BFS (Строим новые уровни от истока 0):

   • level = 0

   • Из 0 можно попасть только в 1 (ёмкость 1). Значит:

     • level[1] = 1

   • Из 1 можно попасть в 2 (ёмкость 5). Значит:

     • level[2] = 2

   • Из 2 можно попасть в 3 (ёмкость 1). Значит:

     • level[3] = 3

   • Сток 3 достижим (level[3] = 3), продолжаем.

   Уровни: 0:0, 1:1, 2:2, 3:3.

2. DFS (Ищем блокирующий поток):

   • Начинаем из 0.

   • Путь 0 → 1 (ёмкость 1). Идём дальше из 1.

   • Путь 1 → 2 (ёмкость 5). Идём дальше из 2.

   • Путь 2 → 3 (ёмкость 1). Дошли до стока 3!

   • Минимальная ёмкость на пути 0 → 1 → 2 → 3 это min(1, 5, 1) = 1. Отправляем 1 единицу потока.

     • Ёмкость 0 → 1 становится 1 - 1 = 0.

     • Ёмкость 1 → 2 становится 5 - 1 = 4.

     • Ёмкость 2 → 3 становится 1 - 1 = 0.

     • Ёмкость обратных рёбер увеличивается.

   • Из 0 больше нет путей по уровням. Блокирующий поток для этой итерации: 1.

   • Общий поток = 4 + 1 = 5.

Итерация 3:

1. BFS (Строим новые уровни от истока 0):

   • level = 0

   • Из 0 больше нельзя попасть никуда (все прямые рёбра из 0 имеют ёмкость 0).

   • Сток 3 недостижим. Алгоритм завершается.

Максимальный поток = 5.

5. Код на C# с подробными комментариями

Теперь давайте посмотрим, как это всё выглядит в коде на языке C#. Код хорошо прокомментирован, чтобы вы могли понять каждую строчку.

// Алгоритм Диница (Dinic) — поиск максимального потока в сети

using System;
using System.Collections.Generic;

namespace DinicMaxFlow
{
    /// <summary>Структура ребра остаточного графа.</summary>
    public class Edge
    {
        public int  To;   // куда ведёт ребро
        public int  Rev;  // индекс обратного ребра в _g[To]
        public long Cap;  // остаточная ёмкость

        public Edge(int to, int rev, long cap)
        {
            To  = to;
            Rev = rev;
            Cap = cap;
        }
    }

    /// <summary>Реализация алгоритма Диница.</summary>
    public class Dinic
    {
        private readonly List<Edge>[] _g; // граф
        private readonly int          _n; // |V|
        private int[] _level;             // уровни после BFS
        private int[] _it;                // «указатели» DFS

        public Dinic(int n)
        {
            _n = n;
            _g = new List<Edge>[n];
            for (int i = 0; i < n; i++)
                _g[i] = new List<Edge>();
        }

        /// <summary>Добавляет directed-edge from → to ёмкостью cap.</summary>
        public void AddEdge(int from, int to, long cap)
        {
            Edge fwd = new Edge(to,   _g[to].Count,   cap);
            Edge rev = new Edge(from, _g[from].Count, 0);
            _g[from].Add(fwd);
            _g[to].Add(rev);
        }

        /// <summary>Максимальный поток из s в t.</summary>
        public long MaxFlow(int s, int t)
        {
            long flow = 0;
            const long INF = long.MaxValue / 4;

            while (Bfs(s, t))
            {
                _it = new int[_n];
                long pushed;
                while ((pushed = Dfs(s, t, INF)) > 0)
                    flow += pushed;
            }
            return flow;
        }

        // ---------- внутренние шаги ----------

        private bool Bfs(int s, int t)
        {
            _level = new int[_n];
            Array.Fill(_level, -1);

            Queue<int> q = new Queue<int>();
            _level[s] = 0;
            q.Enqueue(s);

            while (q.Count > 0)
            {
                int v = q.Dequeue();
                foreach (var e in _g[v])
                {
                    if (e.Cap > 0 && _level[e.To] < 0)
                    {
                        _level[e.To] = _level[v] + 1;
                        q.Enqueue(e.To);
                    }
                }
            }
            return _level[t] >= 0;
        }

        private long Dfs(int v, int t, long f)
        {
            if (v == t) return f;

            for (int i = _it[v]; i < _g[v].Count; i++, _it[v] = i)
            {
                Edge e = _g[v][i];
                if (e.Cap <= 0 || _level[v] + 1 != _level[e.To]) continue;

                long pushed = Dfs(e.To, t, Math.Min(f, e.Cap));
                if (pushed <= 0) continue;

                e.Cap -= pushed;
                _g[e.To][e.Rev].Cap += pushed;
                return pushed;
            }
            return 0;
        }
    }

    internal static class Program
    {
        private static void Main()
        {
            // Демонстрационный граф:
            int n = 4;
            Dinic dinic = new Dinic(n);

            dinic.AddEdge(0, 1, 3);
            dinic.AddEdge(0, 2, 2);
            dinic.AddEdge(1, 2, 5);
            dinic.AddEdge(1, 3, 2);
            dinic.AddEdge(2, 3, 3);

            Console.WriteLine($"Максимальный поток = {dinic.MaxFlow(0, 3)}"); // → 5
        }
    }
}

6. Заключение

Алгоритм Диница — это не просто набор сложных формул, а элегантное решение для задач, которые встречаются повсюду: от логистики и сетевого планирования до компьютерной графики и даже машинного обучения. Понимание таких алгоритмов не только расширяет ваш кругозор как программиста, но и развивает логическое мышление, что очень важно в IT.

Надеемся, эта статья помогла вам «разжевать» алгоритм Диница и понять его суть. Теперь вы можете смело экспериментировать с кодом, менять графы и смотреть, как он работает! Удачи в ваших дальнейших исследованиях!