Flujo máximo - algoritmo de Dinic

El algoritmo de Dinic resuelve el problema de flujo máximo en $O(V^2E)$. El problema de flujo máximo se define en este artículo Flujo máximo - Ford-Fulkerson y Edmonds-Karp. Este algoritmo fue descubierto por Yefim Dinitz en 1970.

Definiciones

Una red residual $G^R$ de una red $G$ es una red que contiene dos aristas por cada arista $(v, u)\in G$:

• $(v, u)$ con capacidad $c_{vu}^R = c_{vu} - f_{vu}$
• $(u, v)$ con capacidad $c_{uv}^R = f_{vu}$

Un flujo bloqueante (blocking flow) de alguna red es un flujo tal que todo camino de $s$ a $t$ contiene al menos una arista saturada por este flujo. Nótese que un flujo bloqueante no es necesariamente máximo.

Una red por capas (layered network) de una red $G$ es una red construida de la siguiente forma. Primero, para cada vértice $v$ calculamos $level[v]$: el camino más corto (sin pesos) de $s$ a este vértice usando solo aristas con capacidad positiva. Luego conservamos solo aquellas aristas $(v, u)$ para las que $level[v] + 1 = level[u]$. Obviamente, esta red es acíclica.

Algoritmo

El algoritmo consiste en varias fases. En cada fase construimos la red por capas de la red residual de $G$. Luego encontramos un flujo bloqueante arbitrario en la red por capas y lo sumamos al flujo actual.

Demostración de corrección

Mostremos que si el algoritmo termina, encuentra el flujo máximo.

Si el algoritmo terminó, no pudo encontrar un flujo bloqueante en la red por capas. Eso significa que la red por capas no tiene ningún camino de $s$ a $t$. Eso significa que la red residual no tiene ningún camino de $s$ a $t$. Eso significa que el flujo es máximo.

Número de fases

El algoritmo termina en menos de $V$ fases. Para demostrarlo, primero hay que probar dos lemas.

Lema 1. Las distancias de $s$ a cada vértice no disminuyen después de cada iteración, es decir, $level_{i+1}[v] \ge level_i[v]$.

Demostración. Fijemos una fase $i$ y un vértice $v$. Consideremos cualquier camino más corto $P$ de $s$ a $v$ en $G_{i+1}^R$. La longitud de $P$ es igual a $level_{i+1}[v]$. Nótese que $G_{i+1}^R$ solo puede contener aristas de $G_i^R$ y aristas inversas de aristas de $G_i^R$. Si $P$ no tiene aristas inversas respecto de $G_i^R$, entonces $level_{i+1}[v] \ge level_i[v]$ porque $P$ también es un camino en $G_i^R$. Ahora, supongamos que $P$ tiene al menos una arista inversa. Sea la primera de esas aristas $(u, w)$. Entonces $level_{i+1}[u] \ge level_i[u]$ (por el primer caso). La arista $(u, w)$ no pertenece a $G_i^R$, así que la arista $(w, u)$ fue afectada por el flujo bloqueante en la iteración anterior. Eso significa que $level_i[u] = level_i[w] + 1$. Además, $level_{i+1}[w] = level_{i+1}[u] + 1$. De estas dos ecuaciones y $level_{i+1}[u] \ge level_i[u]$ obtenemos $level_{i+1}[w] \ge level_i[w] + 2$. Ahora podemos usar la misma idea para el resto del camino.

Lema 2. $level_{i+1}[t] > level_i[t]$

Demostración. Por el lema anterior, $level_{i+1}[t] \ge level_i[t]$. Supongamos que $level_{i+1}[t] = level_i[t]$. Nótese que $G_{i+1}^R$ solo puede contener aristas de $G_i^R$ y aristas inversas de aristas de $G_i^R$. Eso significa que hay un camino más corto en $G_i^R$ que no fue bloqueado por el flujo bloqueante. Es una contradicción.

De estos dos lemas concluimos que hay menos de $V$ fases porque $level[t]$ aumenta, pero no puede ser mayor que $V - 1$.

Encontrar un flujo bloqueante

Para encontrar el flujo bloqueante en cada iteración, podemos simplemente intentar empujar flujo con DFS de $s$ a $t$ en la red por capas mientras se pueda empujar. Para hacerlo más rápido, hay que eliminar las aristas que ya no se pueden usar para empujar. Para ello podemos mantener un puntero en cada vértice que apunta a la siguiente arista que se puede usar.

Una sola ejecución de DFS toma tiempo $O(k+V)$, donde $k$ es el número de avances de puntero en esta ejecución. Sumado sobre todas las ejecuciones, el número de avances de puntero no puede exceder $E$. Por otro lado, el número total de ejecuciones no excederá $E$, ya que cada ejecución satura al menos una arista. De esta forma, el tiempo de ejecución total de encontrar un flujo bloqueante es $O(VE)$.

Complejidad

Hay menos de $V$ fases, así que la complejidad total es $O(V^2E)$.

Redes unitarias

Una red unitaria (unit network) es una red en la que para cualquier vértice excepto $s$ y $t$ o bien la arista entrante o bien la saliente es única y tiene capacidad unitaria. Ese es exactamente el caso de la red que construimos para resolver el problema de matching máximo con flujos.

En redes unitarias el algoritmo de Dinic funciona en $O(E\sqrt{V})$. Demostrémoslo.

Primero, cada fase ahora funciona en $O(E)$ porque cada arista se considerará a lo sumo una vez.

Segundo, supongamos que ya ha habido $\sqrt{V}$ fases. Entonces se han encontrado todos los caminos aumentantes con longitud $\le\sqrt{V}$. Sea $f$ el flujo actual, $f’$ el flujo máximo. Consideremos su diferencia $f’ - f$. Es un flujo en $G^R$ de valor $|f’| - |f|$ y en cada arista es $0$ o $1$. Se puede descomponer en $|f’| - |f|$ caminos de $s$ a $t$ y posiblemente ciclos. Como la red es unitaria, no pueden tener vértices en común, así que el número total de vértices es $\ge (|f’| - |f|)\sqrt{V}$, pero también es $\le V$, así que en otras $\sqrt{V}$ iteraciones encontraremos definitivamente el flujo máximo.

Redes de capacidades unitarias

En un escenario más genérico, cuando todas las aristas tienen capacidades unitarias, pero el número de aristas entrantes y salientes no está acotado, los caminos no pueden tener aristas en común en lugar de vértices en común. De forma similar esto permite demostrar la cota de $\sqrt E$ sobre el número de iteraciones, de modo que el tiempo de ejecución del algoritmo de Dinic en tales redes es a lo sumo $O(E \sqrt E)$.

Finalmente, también es posible demostrar que el número de fases en redes de capacidad unitaria no excede $O(V^{2/3})$, lo que da una estimación alternativa de $O(EV^{2/3})$ en las redes con un número particularmente grande de aristas.

Implementación

struct FlowEdge {
    int v, u;
    long long cap, flow = 0;
    FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
    const long long flow_inf = 1e18;
    vector<FlowEdge> edges;
    vector<vector<int>> adj;
    int n, m = 0;
    int s, t;
    vector<int> level, ptr;
    queue<int> q;

    Dinic(int n, int s, int t) : n(n), s(s), t(t) {
        adj.resize(n);
        level.resize(n);
        ptr.resize(n);
    }

    void add_edge(int v, int u, long long cap) {
        edges.emplace_back(v, u, cap);
        edges.emplace_back(u, v, 0);
        adj[v].push_back(m);
        adj[u].push_back(m + 1);
        m += 2;
    }

    bool bfs() {
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int id : adj[v]) {
                if (edges[id].cap == edges[id].flow)
                    continue;
                if (level[edges[id].u] != -1)
                    continue;
                level[edges[id].u] = level[v] + 1;
                q.push(edges[id].u);
            }
        }
        return level[t] != -1;
    }

    long long dfs(int v, long long pushed) {
        if (pushed == 0)
            return 0;
        if (v == t)
            return pushed;
        for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
            int id = adj[v][cid];
            int u = edges[id].u;
            if (level[v] + 1 != level[u])
                continue;
            long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
            if (tr == 0)
                continue;
            edges[id].flow += tr;
            edges[id ^ 1].flow -= tr;
            return tr;
        }
        return 0;
    }

    long long flow() {
        long long f = 0;
        while (true) {
            fill(level.begin(), level.end(), -1);
            level[s] = 0;
            q.push(s);
            if (!bfs())
                break;
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, flow_inf)) {
                f += pushed;
            }
        }
        return f;
    }
};

Problemas de práctica

• SPOJ: FASTFLOW