Problema de ruta de máxima capacidad con restricciones

Question

Estaba tratando de desarrollar un algoritmo para un problema de máxima capacidad con restricciones, pero no podía descubrir los cambios necesarios requeridos para la salida correcta. El problema es:

Dado un gráfico no dirigido con dos parámetros (peso, costo).Tenemos que encontrar el El problema de la ruta de capacidad máxima de la fuente a destino, de modo que el costo de la ruta (suma de los bordes de la ruta) esté dentro de un valor fijo especificado por el usuario.En otras palabras, es (suma del parámetro de costo a lo largo de la ruta) es superior delimitado por un valor constante.
Modificé el algoritmo existente al agregar y restricción de costos adicionales al relajarme los bordes, pero no pudo hacer que funcione para todo tipo de gráficos.También me preguntaba si este problema es NP-Completo.

Answer 1

Se puede resolver en tiempo polinomial.Por ejemplo, puede utilizar la búsqueda binaria sobre el peso.Dado un peso candidato, elimine todos los bordes con menor peso, luego encuentre la ruta de costo más bajo y pruebe si su costo está por debajo del límite inferior;Eso te dice si el peso era demasiado alto o demasiado bajo.Repita hasta que convergues la búsqueda binaria.