Edmonds-Karp Algoritmo para un gráfico que tiene nodos con capacidades de flujo

Question

Estoy implementando este algoritmo para un gráfico dirigido. Pero lo interesante de estos nodos gráficos también tiene sus propias capacidades de flujo. Creo que este cambio sutil del problema original debe manejarse de una manera especial. Porque, en el problema original de flujo máximo, estaba bien encontrar un camino de principio a fin (de hecho, en el algoritmo Edmonds-Karp, necesitamos hacer BFS, y elegir la primera ruta que llegue al nodo final) Pero con este nodo: extensión de capacidad, tenemos que ser más cuidadosos con el trabajo de 'selección de ruta'. Lo sé porque implementé el algoritmo original y me encontré obteniendo valores de flujo más pequeños que el flujo máximo, dudo que tenga que ver con las restricciones de capacidad de este nodo.

Puse mucho esfuerzo en esto y se me ocurrieron algunas ideas como transformar el gráfico inicial en un gráfico que no tiene restricción de capacidad en los nodos al agregar auto bucles (agregando loops a cada nodo y encontrar caminos que incluyen este auto -loops para cada nodo en la ruta) o agregar nodos virtuales y bordes cuyos pesos reemplazan las restricciones iniciales de capacidad de nodo) Sin embargo, no estoy convencido de que alguna de estas sea una buena solución para este problema.

Cualquier idea sería muy apreciada.

Gracias de antemano.

Answer 1

Hay una simple reducción del problema de flujo máximo con capacidades de nodo a un problema de flujo máximo normal:

Para cada vértice v en el gráfico, reemplace con dos vértices v_in y v_out. Cada borde entrante a v debe apuntar a v_in y cada borde saliente de v debe apuntar desde v_out. A continuación, cree una ventaja adicional desde v_in hasta v_out con capacidad c_v, la capacidad del vértice v.

Así que solo ejecuta Edmunds-Karp en el gráfico transformado.

Digamos que usted tiene la siguiente gráfica en su problema (vértice v tiene capacidad de 2):

s --> v --> t 
    1 2 1 

Esto correspondería a este gráfico en el problema de flujo máximo:

s --> v_in --> v_out --> t 
    1  2   1 

Debería ser evidente que el máximo flujo obtenido es la solución (y tampoco es particularmente difícil de probar).