Problème de chemin de capacité maximum avec contraintes

Question

J'essayais de développer un algorithme pour un problème de capacité maximum avec des contraintes, mais je ne pouvais pas comprendre les modifications nécessaires requises pour une sortie correcte. Le problème est de:
Compte tenu d'un graphique non dirigé avec deux paramètres (poids, coût).Nous devons trouver le Problème de chemin de capacité maximum de la source à destination telle que le coût du chemin (somme des bords du chemin) se situe dans une valeur fixe spécifiée par l'utilisateur.En d'autres termes, il (la somme du paramètre de coût le long du trajet) est limitée supérieure par une valeur constante.
J'ai modifié l'algorithme existant en ajoutant et en ajoutant des contraintes de coûts supplémentaires tout en relaxant les bords, mais qu'il était incapable de le faire fonctionner pour tous les types de graphique.Je me demandais également si ce problème est NP-complet.

Answer 1

Il peut être résolu en temps polynomial.Par exemple, vous pouvez utiliser une recherche binaire sur le poids.Compte tenu d'un poids candidat, supprimez toutes les bords avec un poids inférieur, puis trouvez le chemin de coût le plus bas et testez si son coût est inférieur à la limite inférieure;Cela vous dit si le poids était trop élevé ou trop bas.Répéter jusqu'à ce que la recherche binaire converge.