Planteamiento y contexto
Cada arista dirigida tiene una capacidad y un costo unitario. Envía hasta un límite de flujo desde s hacia t, minimizando el costo entre las soluciones con el mismo flujo. Devuelve el flujo real y el costo mientras manejas aristas residuales inversas, costos negativos, aristas paralelas, sumideros inalcanzables y desbordamiento de enteros (integer overflow).
Qué está evaluando el entrevistador
- Si construyes correctamente las aristas residuales y los costos inversos.
- Si puedes utilizar caminos más cortos sucesivos (successive shortest paths) o potenciales con aristas negativas.
- Si separas el objetivo de flujo máximo del criterio de desempate de costo mínimo.
- Si especificas la complejidad, los límites de desbordamiento y las pruebas basadas en propiedades (property-based tests).
Preguntas para aclarar antes de responder
Confirma si las capacidades y costos son enteros, si se permiten ciclos de costo negativo, los requisitos de límite exacto, el tamaño del grafo y los límites de los costos. Si se permiten ciclos negativos, aclara si la reducción ilimitada de costos forma parte del modelo y cómo se obtienen los potenciales iniciales.
Estructura de respuesta en 30 segundos
Para cada arista de entrada, añade una arista residual directa y una arista inversa de capacidad cero con el costo negado. Encuentra repetidamente el camino más corto de s a t en el grafo residual y aumenta su cuello de botella hasta alcanzar el límite o hasta que no quede ningún camino. Si los costos pueden ser negativos, calcula los potenciales iniciales con Bellman-Ford y luego recalcula los pesos de las aristas para que Dijkstra sea válido. La complejidad depende de los aumentos y de la implementación del camino más corto, no solo de la complejidad del flujo máximo ordinario.
Análisis detallado paso a paso
1. Estructura de aristas residuales
Almacena el destino, el índice inverso, la capacidad residual y el costo. El aumento disminuye la capacidad directa, incrementa la capacidad inversa y suma el flujo multiplicado por el costo al total. Las aristas inversas permiten que los caminos posteriores deshagan decisiones anteriores, lo cual es fundamental para obtener un costo óptimo.
2. Caminos más cortos y potenciales
Con costos no negativos, Dijkstra es suficiente. Con costos negativos pero sin ciclos negativos, mantén un potencial por vértice, calcula los caminos más cortos usando costos reducidos y luego actualiza los potenciales. Nunca apliques Dijkstra ordinario directamente a un grafo que contenga aristas negativas.
3. Aumento y condición de parada
La cantidad de aumento es el mínimo entre el límite restante, el cuello de botella del camino y cualquier tope por lote. Detén el algoritmo cuando no exista ningún camino y devuelve el flujo real; si se requiere el límite exacto, reporta la no factibilidad (infeasibility). Utiliza un tipo de entero amplio y verifica la multiplicación antes de acumular el costo.
Respuesta de ejemplo de alta calidad
Almacenaría las aristas residuales en listas de adyacencia y añadiría cada par directo e inverso en conjunto. El bucle principal encuentra un camino más corto de s a t entre las aristas con capacidad positiva, lo aumenta y actualiza el costo. Dijkstra funciona para costos no negativos; con costos negativos y sin ciclos negativos, calcula potenciales iniciales y mantén los costos reducidos como no negativos. Limita cada aumento por la demanda restante y el cuello de botella del camino. Si el sumidero se vuelve inalcanzable, devuelve el flujo real y marca el objetivo no alcanzado como no factible. Las pruebas cubren la cancelación inversa, aristas paralelas, capacidad cero, costos negativos, grafos desconectados, flujo parcial, suposiciones de ciclos negativos y desbordamiento por costos grandes. El modelo coincide con la formulación de flujo de costo mínimo de OR-Tools, pero la complejidad debe especificar los factores de vértices, aristas y aumentos; no es automáticamente polinomial en capacidades numéricas.
Errores comunes
- Olvidar las aristas inversas o asignarles un costo positivo en lugar de negado.
- Ejecutar Dijkstra directamente cuando las aristas residuales pueden tener un costo negativo.
- Aumentar solo una unidad por camino más corto sin justificación.
- Tratar el flujo máximo y el costo mínimo como una única clave de ordenamiento indiferenciada.
- Acumular valores grandes de capacidad multiplicada por costo en un tipo de entero estrecho.
Preguntas de seguimiento y respuestas
¿Por qué una arista inversa puede corregir una decisión anterior?
Representa la retirada de un flujo enviado previamente y niega el costo de ese flujo. Un camino más corto posterior puede utilizarla para reorganizar la solución y reducir el costo total.
¿Cuándo necesitas Bellman-Ford?
Cuando el grafo residual inicial tiene aristas de costo negativo pero ningún ciclo negativo, úsalo o usa un método equivalente para calcular los potenciales iniciales; después de esto, los costos reducidos no negativos permiten usar Dijkstra.
¿Qué pasa si no se puede alcanzar el flujo solicitado?
Detén el algoritmo y devuelve el flujo y costo reales con un resultado explícito de no factible. Si el negocio requiere alcanzar el objetivo, la parte que realiza la llamada debe revertir los cambios o elegir una red alternativa en lugar de tratar el flujo parcial como un éxito.