私は非循環有向グラフでソースとシンク（t）の間の最短経路を探しています。グラフには位相的な順序（時間的）があります。すべてのエッジが負または無コストです。 Dijkstraアルゴリズムを使用することはまだ可能ですか？ グラフは次のようになります。graph example 通常、ノードは1回しか探索されないため（コストが増加すると仮定して）、ダイクストラは負の重みでは機能しません。 この場合、負の値（またはコストはゼロ）しかないので、コストは減少するだけです。トポロジカルな順序に従ってグラフを探索すると、パスが最適であることが保証されますか？ Dijkstraのアルゴリズム - DAG負のコストを伴う最短経路
あなたははい、それが最適になりますありがとうございました - それはダイクストラ法ではありません。
Dijkstraのアルゴリズムは、現在の重みに従ってノードを探索する方法を指定します。 original articleから：
セットの最短分岐IIはこのセットから除去され、1つのノードがIを設定する集合Bから転送された結果 セットIに加えました。
あなたが記述していることは別のソリューションであり、そしてそれが動作：今すぐ
D[source] = 0
D[v] = min {D[u] + w(u,v) | u in V}
、あなたはトポロジカル順序を以下しているので、あなたは上記の式が正しい誘導によって証明することができます - 誘導を想定しているのですべてのuがvの前に探索されているという仮説は正しいですが、D[v]も正しい（再開されないため）という結論が成り立ちます。
P.S.この証明は、負の重みだけの仮定を必要としなくても、重みが混合されているとうまくいくので、同じ解が成り立ちます。
したがって、あなたが見ているのは、正の重みを持つグラフ上で最も長いパスです（各値の逆を取るだけです）。この問題は実際には一般的なグラフではNP困難ですが、グラフが有向非循環グラフであれば線形時間で解くことができます。非常に良い説明は例えばhereです。