path - 有向非巡回グラフの最短ポジティブ パス

Question

s の入次数と t の出次数が 0 であるエッジと 2 つの特定のノード s と t に任意の重みを付けた有向非巡回グラフが与えられます。正のコストを持つ s から t への最短経路を決定する方法?

Answer 1

結果の最短パス コストが <0 である場合、<0 ではないコストに到達するまで、グラフからエッジを削除する変更された Bellman-Ford を使用します。