algorithm - 有向非巡回グラフで最も重みのある '5' パスを見つけるにはどうすればよいですか?

Question

各ノードに重みが関連付けられた有向非巡回グラフ (DAG) があります。パスの重みがそのノードのすべての重みの合計として定義される、上位 'n' (たとえば 5) の最も重みのあるパスを見つけたいと考えています。どうすればこれを達成できますか?

精度は望ましいですが、パフォーマンスのために犠牲になる可能性があります。潜在的に、グラフには 10,000 以上のノードやエッジが含まれる可能性があります。

編集：重みはゼロ以上の数値になります。

Answer 1

1. グラフをトポロジカルに並べ替えます。
2. 各グラフのノードを n 要素の優先キュー (最小ヒープ) に関連付けます。
3. ノードごとに (ソート順で)、優先度キューからパスの重みをポップし、ノードの重みを追加して、すべての子孫に渡します。ノードが親から重みを受け取ると、関連付けられた優先キューに挿入する必要があります。
4. リーフ ノードごとに、優先度キューからパスの重みをポップし、ノードの重みを追加して、それらを 1 つの共通の優先度キューに挿入します。最後のノードが処理された後、このプライオリティ キューには、「n」個の最も重要なパスの重みが含まれます。重みとともにバック ポインターを保存すると、これらのパスを復元できます。