私は数百万の頂点とエッジを持つ有向グラフを持っています。頂点の集合が与えられ、それらが「START_POINTS」と呼ばれると仮定しよう。 「END_POINTS」と呼ばれるもう1組の頂点も与えられる。問題は、どのSTART_POINTSからどのEND_POINTSに到達できるかを見つけることです。ここで有向グラフでの効率的な検索
は一例です：
START_POINTS: S1 S2 S3 S4 S5 S6 S7 ...
END_POINTS : E1 E2 E3 E4 E5 E6 E7 ...
アルゴリズムは次のことを伝えることができる必要があります：
S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....
END_POINTSの一部は、任意のSTART_POINTから到達されない場合があります。
ここで問題は、それを実装する最も効率的な方法は何ですか？
各START_POINTから順番に1つずつ試してみましたが、深さ優先検索（またはBFSでは実行時間を大幅に変更します）を使用して到達可能なEND_POINTSを検索しました。しかし、多くのSTART_POINTS（END_POINTSもたくさんあるため）には多くの時間がかかります。
START_POINTSのトレースされたパスの間に大きなオーバーラップがあるため、検索を最適化できます。どのパスがどのEND_POINTSに到達できるかを覚えておく必要があります。これを達成する最も効率的な方法は何ですか？これはよく知られている問題かもしれませんが、まだ解決策を見つけることができませんでした。 1月6日に
EDIT：
私は（キース・ランドールが提案されているものと同様の方法で）高帯域幅のアイデアを実装しようとした：各ノードで、このノードがある場合に開始または終了ポイントのすべてを接続しません出力を入力し、ノードを削除します。
foreach NODE in NODES
Skip if NODE is START_POINT or END_POINT
foreach OUTPUT_NODE of NODE
Disconnect NODE from INPUT_NODE
end
foreach INPUT_NODE of NODE
Disconnect NODE from INPUT_NODE
foreach OUTPUT_NODE of NODE
Connect INPUT_NODE to OUTPUT_NODE
end
end
Remove NODE from NODES
end
これは非常に高速起動し、すぐに非常に遅くなり、残りのノードの入力/出力数はループのために非常に大きく、ネストされた取得する主な理由は、パフォーマンスを殺します。どのようにしてより効率的にすることができますか？
このメソッドを実装し、結果を取得します。 – Yilmaz