DAGのノードを通過する最短パスの数を数えます

Question

DAG内の特定のノードを横断するパスの数をカウントするアルゴリズム（ 'betweenness'の概念に似ています）と、次の条件制約：

すべてのノードではなく、グラフの中のソース/デスティネーションノードの集合のカウントを行う必要があります。すなわち、中間ノードnの場合、ノードのセットからいくつかの最短のパスを知りたいSはノードDのセットをnに渡します（別名では、少なくとも1つの非共通ノードを持つ2つのパスすべてを意味します）。

DAGが存在する可能性があることを考慮して、非常に大きいが縁が乏しく、鶏ノードのディープネストされたループには優先順位が与えられません。

Answer 1

Src/Destノードの各ペアに対して、幅広い最初の検索を使用して、パス内に与えられたノードを持つものを表示できます。最短パスを見つけたら、パスを増やしてサイズを増やすまで、キューを空にし続けるように、検索を少し修正する必要があります。この方法では、複数の最短パスがある場合、ランダムチャンスに縛られることはありません。もちろん、これは重み付けされていないグラフのオプションに過ぎません。