Maximales Kapazitätspfadproblem mit Einschränkungen

Question

Ich versuchte, einen Algorithmus für ein Problem mit maximaler Kapazität mit Einschränkungen zu entwickeln, konnte jedoch die erforderlichen Änderungen nicht herausfinden, die für die korrekte Ausgabe erforderlich sind. Das Problem ist:
Gegeben eines ungerechten Diagramms mit zwei Parametern (Gewicht, Kosten).Wir müssen das Maximaler Kapazitätspfadproblem von der Quelle zum Ziel, so dass die Kosten des Pfads (Summe der Ränder des Pfads) innerhalb eines vom Benutzer angegebenen festen Wert liegt.Mit anderen Worten, es (Summe des Kostenparameters entlang des Pfads) ist mit einem konstanten Wert überschritten.
Ich habe den bestehenden Algorithmus durch Zugabe und zusätzliche Kosteneinschränkungen geändert, während er die Ränder entspannte, konnte sie jedoch nicht für alle Arten von Graphen arbeiten lassen.Ich habe mich auch gefragt, ob dieses Problem np-komplett ist.

Answer 1

Es kann in der Polynomzeit gelöst werden.Zum Beispiel können Sie eine binäre Suche über das Gewicht verwenden.Löschen eines Kandidatengewichts alle Kanten mit geringem Gewicht, dann finden Sie den niedrigsten Pfad und testen Sie, ob die Kosten unter der unteren Grenze liegen;Das sagt Ihnen, ob das Gewicht zu hoch oder zu niedrig war.Wiederholen, bis die binäre Suche konvergiert.