Estoy implementando este algoritmo para un gráfico dirigido. Pero lo interesante de este nodo gráfico 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 cualquier ruta de principio a fin (en realidad, en el algoritmo Edmonds-Karp, necesitamos hacer BFS y elegir la primera ruta que llega al nodo final) Pero con este nodo- ampliación de capacidad, debemos ser más cuidadosos con el trabajo de 'esta 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 estas restricciones de capacidad de nodo.

Puse mucho esfuerzo en esto y se me ocurrieron algunas ideas como transformar el gráfico inicial en un gráfico que no tenga restricciones de capacidad en los nodos al agregar bucles automáticos (agregar bucles automáticos a cada nodo y encontrar rutas que incluyan estos bucles automáticos para cada nodo en la ruta) o agregando nodos virtuales y bordes cuyos pesos reemplazan las restricciones iniciales de capacidad de nodo) Sin embargo, no estoy convencido de que ninguno de estos sea una buena solución para este problema.

Cualquier idea sería muy apreciada.

Gracias por adelantado