効率的かどうかを知りたいS内のすべての経路がVの頂点vを含むように、DAG G =（V、E）の部分グラフS outを構築するアルゴリズムS = F（v、G）を生成する。 F "（N、G）を作成します。DAG Gを最初に格納するための任意のデータ構造が公開されています。
実際には、追加するのを忘れた状態は、Gは入力エッジのない一意の頂点rを持ち、パスは出て行くエッジのない頂点である形式でなければなりません。
私が見逃した別の条件は、もしwがシンクであるならば、すべてのv、wに対してNのすべてのwに対して、F "（N、G）パス<r、..、v、..、x>ここでx！= w。
私は実際には1つの解決策を持っていますが、＃V> 2000と＃N> 2のときにはスケールされません。
回答：
回答№1は1私はあなたがG =（{r} + V + {d}、E）の最大部分グラフSを探していると仮定します。ここで、rは固有のソースノード、dはシンクです。ノードv。
私の提案アルゴリズム：
例えばrとvとの間のすべての経路を見つける。答えは 与えられた2つのノード間のパスを探しますか？
vとの間のすべてのパスを見つけるアルゴリズム。 Gは非周期的なので、vからdへの経路は、ステップ1で既に見つかった経路に戻ることができない。したがって、結果のグラフでは、rとdの間のすべての経路はvを通過する。
回答№2の場合は1
結果のグラフには到達可能なノードが含まれていますノードvから到達可能である（または、転置されたサブグラフにおいてvから到達可能なノード）。到達可能なノードのセットを効率的に取得することができます。
これは、一連のノードに対して簡単に拡張できます。幅優先検索の開始時にすべてを追加するだけです。