制約に関する最大容量パス問題

Question

私は制約の最大容量問題のためのアルゴリズムを開発しようとしていましたが、正しい出力に必要な変更の変更を把握できませんでした。 問題は次のとおりです。
2つのパラメータ（重量、コスト）を持つ無向グラフが与えられます。ソースから宛先への最大容量パス問題（パスのエッジの合計）がユーザーによって指定された固定値内にあるように。言い換えれば、それ（経路に沿ったコストパラメータの合計）は一定値で上限されています。
エッジをリラックスしながら、すべてのタイプのグラフに対して機能させることができなかったが、追加料金の制約を追加して既存のアルゴリズムを変更しました。この問題がNP-Completeであるかどうか疑問に思っていました。

Answer 1

多項式時間で解決することができます。たとえば、重みにバイナリ検索を使用できます。候補重みを考えると、低い重みですべてのエッジを削除してから、最低コストのパスを見つけ、そのコストが下限下にあるかどうかをテストします。それは体重が高すぎるか低すぎたかをあなたに知らせます。バイナリ検索が収束するまで繰り返します。