6

次の条件と制約を使用して、DAG 内の特定のノードを横切るパスの数をカウントするアルゴリズムを探しています (「間」の概念に似ています)。

グラフ内のソース/宛先ノードのセットのカウントを行う必要があり、すべてのノード、つまり中間ノード n の場合ではありません。ノード S のセットからノード D のセットへの個別の最短パスの数を知りたいです。 n まで (そして個別とは、少なくとも 1 つの非共通ノードを持つ 2 つのパスごとを意味します)

DAG が非常に大きくてもエッジがまばらである可能性があるため、ノード上の深いネストされたループが優先されないことを考慮して、これを行うために提案できるアルゴリズムは何ですか。

4

1 に答える 1

3

Src/Dest ノードの各ペアに対して幅優先検索を使用して、指定したノードがパスに含まれているノードを確認できます。最短パスを見つけたら、サイズを大きくするパスに到達するまでキューを空にし続けるように、検索を少し変更する必要があります。このようにして、最短経路が複数ある場合でも偶然に縛られることはありません。もちろん、これは重み付けされていないグラフのみのオプションです。

于 2011-09-23T20:41:41.103 に答える