graph - ダイクストラを使用して有向グラフで負のサイクルを見つけますか?

Question

負のエッジ (u,v) を持つ有向グラフ G=(v,e) があります。他のすべてのエッジは正です。

ダイクストラを使用して負のサイクルを見つけるにはどうすればよいですか?

Answer 1

(u,v)グラフから削除します。vからへの最短経路を見つけますu(Dijkstra を使用)。総重量が 未満-w(u,v)の場合、負のサイクルが見つかりました。そうでなければ、そのようなサイクルは存在しません。