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