Flujo de costo mínimo - algoritmo de caminos más cortos sucesivos

Dada una red $G$ que consiste de $n$ vértices y $m$ aristas. Para cada arista (en general, aristas orientadas, pero véase abajo), se dan la capacidad (un entero no negativo) y el costo por unidad de flujo a lo largo de esta arista (algún entero). También están marcados la fuente $s$ y el sumidero $t$ .

Para un valor dado $K$ , hay que encontrar un flujo de esta cantidad, y entre todos los flujos de esta cantidad hay que elegir el flujo con el menor costo. Esta tarea se llama problema de flujo de costo mínimo (minimum-cost flow).

A veces la tarea se da un poco distinto: se quiere encontrar el flujo máximo, y entre todos los flujos máximos queremos encontrar el de menor costo. Esto se llama el problema de flujo máximo de costo mínimo (minimum-cost maximum-flow).

Ambos problemas se pueden resolver de forma efectiva con el algoritmo de caminos más cortos sucesivos.

Algoritmo

Este algoritmo es muy similar al de Edmonds-Karp para calcular el flujo máximo.

Caso más simple

Primero solo consideramos el caso más simple, donde el grafo es orientado, y hay a lo sumo una arista entre cualquier par de vértices (p. ej. si $(i, j)$ es una arista del grafo, entonces $(j, i)$ no puede formar parte de él también).

Sea $U_{i j}$ la capacidad de una arista $(i, j)$ si esta arista existe. Y sea $C_{i j}$ el costo por unidad de flujo a lo largo de esta arista $(i, j)$ . Y finalmente sea $F_{i, j}$ el flujo a lo largo de la arista $(i, j)$ . Inicialmente todos los valores de flujo son cero.

Modificamos la red de la siguiente forma: para cada arista $(i, j)$ agregamos la arista inversa $(j, i)$ a la red con la capacidad $U_{j i} = 0$ y el costo $C_{j i} = -C_{i j}$ . Como, según nuestras restricciones, la arista $(j, i)$ no estaba en la red antes, todavía tenemos una red que no es un multigrafo (grafo con aristas múltiples). Además siempre mantendremos la condición $F_{j i} = -F_{i j}$ cierta durante los pasos del algoritmo.

Definimos la red residual para algún flujo fijo $F$ de la siguiente forma (igual que en el algoritmo de Ford-Fulkerson): la red residual contiene solo aristas no saturadas (es decir, aristas en las que $F_{i j} < U_{i j}$ ), y la capacidad residual de cada una de esas aristas es $R_{i j} = U_{i j} - F_{i j}$ .

Ahora podemos hablar de los algoritmos para calcular el flujo de costo mínimo. En cada iteración del algoritmo encontramos el camino más corto en el grafo residual de $s$ a $t$ . A diferencia de Edmonds-Karp, buscamos el camino más corto en términos del costo del camino en lugar del número de aristas. Si ya no existe un camino, entonces el algoritmo termina, y el flujo $F$ es el deseado. Si se encontró un camino, aumentamos el flujo a lo largo de él tanto como sea posible (es decir, encontramos la capacidad residual mínima $R$ del camino, y aumentamos el flujo en ella, y reducimos las aristas inversas en la misma cantidad). Si en algún momento el flujo alcanza el valor $K$ , entonces detenemos el algoritmo (nótese que en la última iteración del algoritmo es necesario aumentar el flujo solo en una cantidad tal que el valor final del flujo no supere $K$ ).

No es difícil ver que si ponemos $K$ en infinito, entonces el algoritmo encontrará el flujo máximo de costo mínimo. Así que ambas variaciones del problema se pueden resolver con el mismo algoritmo.

Grafos no dirigidos / multigrafos

El caso de un grafo no dirigido o un multigrafo no difiere conceptualmente del algoritmo de arriba. El algoritmo también funcionará en estos grafos. Sin embargo se vuelve un poco más difícil de implementar.

Una arista no dirigida $(i, j)$ es de hecho lo mismo que dos aristas orientadas $(i, j)$ y $(j, i)$ con la misma capacidad y valores. Como el algoritmo de flujo de costo mínimo descrito arriba genera una arista inversa para cada arista dirigida, parte la arista no dirigida en $4$ aristas dirigidas, y de hecho obtenemos un multigrafo.

¿Cómo lidiar con aristas múltiples? Primero el flujo de cada una de las aristas múltiples debe guardarse por separado. Segundo, al buscar el camino más corto, es necesario tener en cuenta que es importante cuál de las aristas múltiples se usa en el camino. Así, en lugar del arreglo usual de ancestros además debemos guardar el número de arista desde la que vinimos junto con el ancestro. Tercero, al aumentar el flujo a lo largo de una cierta arista, es necesario reducir el flujo a lo largo de la arista inversa. Como tenemos aristas múltiples, hay que guardar el número de arista de la arista inversa para cada arista.

No hay otras obstrucciones con grafos no dirigidos o multigrafos.

Complejidad

El algoritmo aquí es en general exponencial en el tamaño de la entrada. Para ser más específicos, en el peor caso puede empujar solo $1$ unidad de flujo en cada iteración, tomando $O(F)$ iteraciones para encontrar un flujo de costo mínimo de tamaño $F$ , haciendo que el tiempo de ejecución total sea $O(F \cdot T)$ , donde $T$ es el tiempo requerido para encontrar el camino más corto de la fuente al sumidero.

Si se usa el algoritmo de Bellman-Ford para esto, el tiempo de ejecución es $O(F mn)$ . También es posible modificar el algoritmo de Dijkstra, de modo que necesite $O(nm)$ de preprocesamiento como paso inicial y luego funcione en $O(m \log n)$ por iteración, haciendo que el tiempo de ejecución total sea $O(mn + F m \log n)$ . Aquí hay un generador de un grafo en el que tal algoritmo requeriría tiempo $O(2^{n/2} n^2 \log n)$ .

El algoritmo de Dijkstra modificado usa los llamados potenciales del algoritmo de Johnson . Es posible combinar las ideas de este algoritmo y el algoritmo de Dinic para reducir el número de iteraciones de $F$ a $\min(F, nC)$ , donde $C$ es el costo máximo encontrado entre las aristas. Se puede leer más sobre potenciales y su combinación con el algoritmo de Dinic aquí .

Implementación

Aquí hay una implementación usando el algoritmo SPFA para el caso más simple.


struct Edge
{
    int from, to, capacity, cost;
};

vector<vector<int>> adj, cost, capacity;

const int INF = 1e9;

void shortest_paths(int n, int v0, vector<int>& d, vector<int>& p) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<bool> inq(n, false);
    queue<int> q;
    q.push(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int v : adj[u]) {
            if (capacity[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
                d[v] = d[u] + cost[u][v];
                p[v] = u;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int min_cost_flow(int N, vector<Edge> edges, int K, int s, int t) {
    adj.assign(N, vector<int>());
    cost.assign(N, vector<int>(N, 0));
    capacity.assign(N, vector<int>(N, 0));
    for (Edge e : edges) {
        adj[e.from].push_back(e.to);
        adj[e.to].push_back(e.from);
        cost[e.from][e.to] = e.cost;
        cost[e.to][e.from] = -e.cost;
        capacity[e.from][e.to] = e.capacity;
    }

    int flow = 0;
    int cost = 0;
    vector<int> d, p;
    while (flow < K) {
        shortest_paths(N, s, d, p);
        if (d[t] == INF)
            break;
        
        // find max flow on that path
        int f = K - flow;
        int cur = t;
        while (cur != s) {
            f = min(f, capacity[p[cur]][cur]);
            cur = p[cur];
        }

        // apply flow
        flow += f;
        cost += f * d[t];
        cur = t;
        while (cur != s) {
            capacity[p[cur]][cur] -= f;
            capacity[cur][p[cur]] += f;
            cur = p[cur];
        }
    }

    if (flow < K)
        return -1;
    else
        return cost;
}