単一始点最短路(Bellman-ford)
説明
単一始点全点間最短路を求めるアルゴリズム。負辺があっても動作する。また負閉路も検出する。
使い方
- bellman_ford(edges, V, s): $V$ 頂点の重み付き有向グラフで辺は $edges$ からなす。頂点 $s$ からすべての頂点への最短距離を求め, その列を返す。負閉路が検出された時空列を返す。
計算量
$O(VE)$
$V$: 頂点数, $E$: 辺数
実装例
単一始点全点間最短路を求めるアルゴリズム。負辺があっても動作する。また負閉路も検出する。
$O(VE)$
$V$: 頂点数, $E$: 辺数