テクノロジ系 / アルゴリズムとプログラミング
ベルマンフォード法
ベルマンフォード法は、負の重みを含むグラフでも使える単一始点最短経路アルゴリズムです。
もう少し詳しく
すべての辺に対して距離の更新を繰り返し、頂点数に応じた回数だけ緩和処理を行います。負閉路がある場合には最短距離が定まらないため、負閉路の検出にも使えます。
試験での見方
例：A→Bが5、A→Cが2、C→Bが-4なら、A→C→Bの距離-2として更新できます。
テクノロジ系 / アルゴリズムとプログラミング
ベルマンフォード法は、負の重みを含むグラフでも使える単一始点最短経路アルゴリズムです。
すべての辺に対して距離の更新を繰り返し、頂点数に応じた回数だけ緩和処理を行います。負閉路がある場合には最短距離が定まらないため、負閉路の検出にも使えます。
例：A→Bが5、A→Cが2、C→Bが-4なら、A→C→Bの距離-2として更新できます。
負の辺、全辺の緩和、負閉路検出が出たらベルマンフォード法です。重みがすべて非負で効率を重視する問題ならダイクストラ法と切り分けます。