問題の説明を結合しました。制約からsからdまでの最短経路を求める。制約は、最短経路コストcが下限を有する、すなわち、コストcが割り当てられた下限Nよりも大きくなければならないが、N以上の可能な経路のすべてのコストにおいて最小でなければならないという制約がある。単一始点最短パスは、より低い最小コストの
私はこの制約でBellman fordのような従来のSSSPアルゴリズムは正しく動作しないことを理解しています。この問題の最も効率的なアルゴリズムは、どのようにして見つけられますか？
パスがサイクルを持つことができないので、散歩をしたいと思うと思います。
残念なことに、この問題はNPCでもある変更の問題として容易にモデル化することができます。
変更の問題：c_i値のN種類のコインがそれぞれ与えられた場合、N個のコインで番号Xを変更できる可能性はありますか？
モデリング：すべてのc_iが偶数であると仮定します（すべてのc_iを二倍にします）。 i番目の頂点が1番目のコインを表すN + 2個の頂点を作成する。= i < = N。また、（N + 1）と（N + 2）番目の頂点は、コスト（c_i/2）。この問題は、NPCであるX以上のコストの最短経路を見つけることに相当します。削減は明らかですが、それ以上の説明が必要な場合は私の回答を編集することができます。
回答にサイクルを許可しますか？ –
グラフが重み付けされておらず、下限が| V | -1に等しいとき、ハミルトニアンパスを見つけるのと同じであるため、この問題はNP困難にならないことが分かります。私は完全な検索で十分だろうと思う。その結果、サイクルが許されるソリューションにもっと興味があります。 – user122049