Bellman-Ford 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /bellman-ford#noredirect を利用してください。
name
Bellman-Ford 法
short description
Bellman-Ford 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。負辺があっても動作する。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。
input
辺重み $c : E \to \mathbb{R}$ 付き有向グラフ $G = (V, E)$ および頂点 $s \in V$
output
各頂点 $t \in V$ に対し $s$-$t$ 最短路長
time complexity
$O(\vert V \vert \cdot \vert E \vert)$

概要

Bellman-Ford 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。負辺があっても動作する。 ある有向辺 $(x, y)$ を使うことで頂点 $y$ への最短経路長が改善するか試し、改善するなら置き換えるという処理 (これを「緩和する」などと言う) を考える。これをすべての辺に対して行うのを 1 セットとし、これを $\vert V \vert - 1$ 回行うのが Bellman-Ford 法である。その後、負閉路が存在していなかったことの確認も行う。 計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。

詳細

(省略)

その他

関連項目