Dado un Node fuente S, un Node sumidero T , dos arrays Cap[ ][ ] y Cost[ ][ ] que representan un gráfico, donde Cap[i][j] es la capacidad de un borde dirigido desde el Node i al Node j y cost[i][j] es el costo de enviar una unidad de flujo a lo largo de un borde dirigido desde el Node i al Node j , la tarea es encontrar un flujo con el flujo máximo de costo mínimo posible del gráfico dado.
Costo mínimo Flujo máximo: Costo mínimo (por unidad de flujo) requerido para entregar la máxima cantidad de flujo posible del gráfico dado.
Ejemplo:
Entrada: S = 0, T = 4, cap[ ][ ] = {{0, 3, 4, 5, 0}, {0, 0, 2, 0, 0}, {0, 0, 0, 4, 1}, {0, 0, 0, 0, 10}, {0, 0, 0, 0, 0}},
costo[ ][ ] = {{0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}}
Salida: 10 1
Explicación :
Para el gráfico dado, Max flow = 10 y Min cost = 1.Entrada: S = 0, T = 4, costo[][] = { { 0, 1, 0, 0, 2 }, { 0, 0, 0, 3, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0 } }
cap[][] = { { 0, 3, 1, 0, 3 }, { 0, 0 , 2, 0, 0 }, { 0, 0, 0, 1, 6 }, { 0, 0, 0, 0, 2 }, { 0, 0, 0, 0, 0 } }
Salida: 6 8
Enfoque:
el ciclo negativo en la red de costos se cicla con la suma de los costos de todos los bordes en el ciclo es negativa. Se pueden detectar utilizando el algoritmo de Bellman Ford . Deben eliminarse porque, en la práctica, no se puede permitir el flujo a través de tales ciclos. Considere un ciclo de costo negativo , si todo el flujo tiene que pasar por este ciclo, el costo total siempre se reduce por cada ciclo completado. Esto daría como resultado un bucle infinito en el deseo de minimizar el costo total . Entonces, cada vez que una red de costos incluye un ciclo negativo, implica que el costo puede minimizarse aún más (fluyendo a través del otro lado del ciclo en lugar del lado actualmente considerado). Un ciclo negativo una vez detectado se elimina haciendo fluir unCapacidad de cuello de botella en todas las aristas del ciclo.
Ahora, mira qué son los Nodes de oferta y demanda:
Nodes de suministro: Son Nodes positivos que se suman al flujo y que producen el flujo.
Nodes de demanda: Son Nodes negativos que se restan del flujo.
Oferta (o demanda) en cada Node = Flujo total que sale del Node – El flujo total que entra al Node
El problema dado se aborda mediante el envío de una capacidad de cuello de botella a todos los bordes del ciclo para encargarse del ciclo negativo. Además, dado que involucra Nodes de demanda, se invoca el algoritmo Bellman Ford .
Siga los pasos a continuación para resolver el problema:
- Almacene la capacidad de un borde y el costo de ese borde en dos arreglos separados.
- Dado el Node de origen S y el Node receptor T , el borde seleccionado p i , los Nodes de demanda d a y la distancia entre los Nodes dist , busque si es posible tener un flujo de S a T .
- Si existe un flujo, calcule la distancia, value = dist + pi – pi[k] – cost[k] .
- Compare los valores de distancia en dist[ ] con value y siga actualizando hasta obtener el flujo mínimo .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java Program to implement
// the above approach
import java.util.*;
public class MinCostMaxFlow {
// Stores the found edges
boolean found[];
// Stores the number of nodes
int N;
// Stores the capacity
// of each edge
int cap[][];
int flow[][];
// Stores the cost per
// unit flow of each edge
int cost[][];
// Stores the distance from each node
// and picked edges for each node
int dad[], dist[], pi[];
static final int INF
= Integer.MAX_VALUE / 2 - 1;
// Function to check if it is possible to
// have a flow from the src to sink
boolean search(int src, int sink)
{
// Initialise found[] to false
Arrays.fill(found, false);
// Initialise the dist[] to INF
Arrays.fill(dist, INF);
// Distance from the source node
dist[src] = 0;
// Iterate until src reaches N
while (src != N) {
int best = N;
found[src] = true;
for (int k = 0; k < N; k++) {
// If already found
if (found[k])
continue;
// Evaluate while flow
// is still in supply
if (flow[k][src] != 0) {
// Obtain the total value
int val
= dist[src] + pi[src]
- pi[k] - cost[k][src];
// If dist[k] is > minimum value
if (dist[k] > val) {
// Update
dist[k] = val;
dad[k] = src;
}
}
if (flow[src][k] < cap[src][k]) {
int val = dist[src] + pi[src]
- pi[k] + cost[src][k];
// If dist[k] is > minimum value
if (dist[k] > val) {
// Update
dist[k] = val;
dad[k] = src;
}
}
if (dist[k] < dist[best])
best = k;
}
// Update src to best for
// next iteration
src = best;
}
for (int k = 0; k < N; k++)
pi[k]
= Math.min(pi[k] + dist[k],
INF);
// Return the value obtained at sink
return found[sink];
}
// Function to obtain the maximum Flow
int[] getMaxFlow(int cap[][], int cost[][],
int src, int sink)
{
this.cap = cap;
this.cost = cost;
N = cap.length;
found = new boolean[N];
flow = new int[N][N];
dist = new int[N + 1];
dad = new int[N];
pi = new int[N];
int totflow = 0, totcost = 0;
// If a path exist from src to sink
while (search(src, sink)) {
// Set the default amount
int amt = INF;
for (int x = sink; x != src; x = dad[x])
amt = Math.min(amt,
flow[x][dad[x]] != 0
? flow[x][dad[x]]
: cap[dad[x]][x]
- flow[dad[x]][x]);
for (int x = sink; x != src; x = dad[x]) {
if (flow[x][dad[x]] != 0) {
flow[x][dad[x]] -= amt;
totcost -= amt * cost[x][dad[x]];
}
else {
flow[dad[x]][x] += amt;
totcost += amt * cost[dad[x]][x];
}
}
totflow += amt;
}
// Return pair total cost and sink
return new int[] { totflow, totcost };
}
// Driver Code
public static void main(String args[])
{
// Creating an object flow
MinCostMaxFlow flow = new MinCostMaxFlow();
int s = 0, t = 4;
int cap[][] = { { 0, 3, 1, 0, 3 },
{ 0, 0, 2, 0, 0 },
{ 0, 0, 0, 1, 6 },
{ 0, 0, 0, 0, 2 },
{ 0, 0, 0, 0, 0 } };
int cost[][] = { { 0, 1, 0, 0, 2 },
{ 0, 0, 0, 3, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0 } };
int ret[] = flow.getMaxFlow(cap, cost, s, t);
System.out.println(ret[0] + " " + ret[1]);
}
}
Python3
# Python3 program to implement
# the above approach
from sys import maxsize
from typing import List
# Stores the found edges
found = []
# Stores the number of nodes
N = 0
# Stores the capacity
# of each edge
cap = []
flow = []
# Stores the cost per
# unit flow of each edge
cost = []
# Stores the distance from each node
# and picked edges for each node
dad = []
dist = []
pi = []
INF = maxsize // 2 - 1
# Function to check if it is possible to
# have a flow from the src to sink
def search(src: int, sink: int) -> bool:
# Initialise found[] to false
found = [False for _ in range(N)]
# Initialise the dist[] to INF
dist = [INF for _ in range(N + 1)]
# Distance from the source node
dist[src] = 0
# Iterate until src reaches N
while (src != N):
best = N
found[src] = True
for k in range(N):
# If already found
if (found[k]):
continue
# Evaluate while flow
# is still in supply
if (flow[k][src] != 0):
# Obtain the total value
val = (dist[src] + pi[src] -
pi[k] - cost[k][src])
# If dist[k] is > minimum value
if (dist[k] > val):
# Update
dist[k] = val
dad[k] = src
if (flow[src][k] < cap[src][k]):
val = (dist[src] + pi[src] -
pi[k] + cost[src][k])
# If dist[k] is > minimum value
if (dist[k] > val):
# Update
dist[k] = val
dad[k] = src
if (dist[k] < dist[best]):
best = k
# Update src to best for
# next iteration
src = best
for k in range(N):
pi[k] = min(pi[k] + dist[k], INF)
# Return the value obtained at sink
return found[sink]
# Function to obtain the maximum Flow
def getMaxFlow(capi: List[List[int]],
costi: List[List[int]],
src: int, sink: int) -> List[int]:
global cap, cost, found, dist, pi, N, flow, dad
cap = capi
cost = costi
N = len(capi)
found = [False for _ in range(N)]
flow = [[0 for _ in range(N)]
for _ in range(N)]
dist = [INF for _ in range(N + 1)]
dad = [0 for _ in range(N)]
pi = [0 for _ in range(N)]
totflow = 0
totcost = 0
# If a path exist from src to sink
while (search(src, sink)):
# Set the default amount
amt = INF
x = sink
while x != src:
amt = min(
amt, flow[x][dad[x]] if
(flow[x][dad[x]] != 0) else
cap[dad[x]][x] - flow[dad[x]][x])
x = dad[x]
x = sink
while x != src:
if (flow[x][dad[x]] != 0):
flow[x][dad[x]] -= amt
totcost -= amt * cost[x][dad[x]]
else:
flow[dad[x]][x] += amt
totcost += amt * cost[dad[x]][x]
x = dad[x]
totflow += amt
# Return pair total cost and sink
return [totflow, totcost]
# Driver Code
if __name__ == "__main__":
s = 0
t = 4
cap = [ [ 0, 3, 1, 0, 3 ],
[ 0, 0, 2, 0, 0 ],
[ 0, 0, 0, 1, 6 ],
[ 0, 0, 0, 0, 2 ],
[ 0, 0, 0, 0, 0 ] ]
cost = [ [ 0, 1, 0, 0, 2 ],
[ 0, 0, 0, 3, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 0 ] ]
ret = getMaxFlow(cap, cost, s, t)
print("{} {}".format(ret[0], ret[1]))
# This code is contributed by sanjeev2552
6 8
Complejidad temporal: O(V 2 * E 2 ) donde V es el número de vértices y E es el número de aristas.
Espacio Auxiliar: O(V)