グラフ操作アルゴリズムの複雑さ

Question

私は指向性と重み付けされたグラフを持っています（負でない値< = 1）。各ノードは最大2度を持つことができます。これには2つの異なるタイプのエッジがあります。私は2つの別個の頂点の間に（1つ目のタイプのエッジを持つ）パスが存在するかどうかを調べる必要があります。存在する場合は、2番目のタイプのエッジを使用して、同じ2つの頂点間のすべてのパスを見つけます。 ..どの方法が効率的なのでしょうか... DFSまたはダイクストラまたはベルマンフォーク..

Answer 1

ここでは重量が必要なのはなぜか分かりません。私が問題を正しく理解しているならば、まずタイプ1のエッジを使って、ノードAからノードBへの少なくとも1つのパスの存在をチェックします。これは、O（| V | + | E |）時間（またはDijkstraまたは類似）のDFSで行うことができます。 2番目の部分はそれほど単純ではなく、すべてのパス（タイプ2のエッジを持つ）が無向変種のNP-hardであることがわかります。つまり、この問題の多項式時間解は存在しません（this related postに記載されています）。実装にリンクするDAG another postの2つのノード間のすべての（可能な指数関数的な）パスを列挙する。