algorithm - 加重 (無向) グラフで 2 つのノード間の長さ X のパスを見つける方法

Question

グラフが与えられた場合、グラフ内の 2 つのノード間の長さ X のパスを見つけるにはどうすればよいですか。パスは、理想的にはエッジを 1 回しか訪れないようにする必要があります。

Answer 1

変更されたBFSアルゴリズムを実装できます。AからBへの最初のパスを見つけると、そのパスの最小の長さがわかります。したがって、Xがこの値よりも小さい場合は、パスが存在することがすでにわかります。

Xがこの値よりも大きい場合は、次のように進めます。見つけたAからBへのパスを調べ、各ノードにBまでの距離で注釈を付けます。

次に、グラフ全体をカバーするまでBFS検索を続けます。

検索がすでに使用されているノードに到達するたびに、それがBにつながるかどうか、また、Bにつながる場合は、そのノードからどれだけ離れているかを確認できます。これにより、見つけたばかりの新しいパスの長さを知ることができ、Xと比較することができます。

ここでも、このパスの各ノードにBまでの距離で注釈を付けます。ノードに複数回注釈を付けることができるようにする必要があります。Bにつながる使用済みノードに到達したら、そのノードのすべての注釈付き値を使用して比較します。

Xより大きい長さのパスにヒットしたときはいつでも、検索を停止できます。