ベルマンフォード法
アルゴリズム図鑑
に掲載の解説が多分いちばん直観的で分かりやすい
メリット
負の経路
が存在しても最短経路を正しく求められる
これは
ダイクストラ法
には無いメリット
デメリット
負の閉路が存在する場合、最短路を求めることが不可能.
ただし負の閉路を検知することは出来る
ノード数を
N
とすると、更新が最悪回数でN-1回で済むはず
N回更新がかかった時点で負の閉路が存在してることになる
負の経路が存在しない場合、最短路を求めるケースにおいて
ダイクストラ法
と比べて計算量が多くなってしまう傾向あり.
任意のノードから別のノードへと探索する際、リーチ可能な全ノードにアクセスして最小値をとるような方法を採ってるため.