初歩的なグラフの問題 (ID:72941)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 ベルマンフォード法は 負の閉路というのが点A→点Bのコストがー４で点B→点Aへのコストが３だとこれも2点の負の閉路になる。 と考えるのでしょうか？ グラフに負の閉路がなければ、ある点Aから出発してAに戻ってきたとき必ずコストが大きくなって帰ってくる。 これが全ての点で成り立つから、ベルマン法で求める最短経路に同じ点は2度と出てこない。 という理解でよいでしょうか？ 数学で読むと難しそうでもコードになるとなんとなく理解できそうな気もします。