DAGで、最高スコアでパスを見つける

Question

各ノードが割り当てられた整数スコアを持つ指向性の非巡回グラフでは、累積スコアが最も高いスタート頂点からのパスを見つける高速な方法は何ですか？私たちが最後から始めて逆方向にグラフを実行し、各ノードで達成可能な最良の累積スコアを保存するDFSアプローチを考えました。結果を印刷するには、最初のノードから始めて、最高の累積スコアを持つ次のノードを貪欲に選択します。しかし、私たちが不親切なグラフを与えられているならば、私たちが同じ道をたくさんの時に横断しているかもしれないので、私はこれが最善の方法であるとは思わない。これをするより良い方法はありますか？

Answer 1

ヒント：トポロジーの順序付けを見つけ、各頂点 $ v $ 、トポロジーの順序付け、最高スコアのパスを計算します。 $ v $ で終わります。