Function cp_library_rs::graph::bellman_ford::bellman_ford
source · pub fn bellman_ford(
N: usize,
start: usize,
edges: &Vec<(usize, usize, isize)>
) -> (bool, Vec<isize>, Vec<usize>)
Expand description
ベルマン・フォード法
- 重み付きグラフの単一始点最短路を求める
- 重みが負の場合にも対応
- 各頂点
v
の距離dist[v]
について- vに到達不可能な場合 →
IINF
- vへの最短路が求まる場合 →
(vへの最短路長)
- vへの最短路がいくらでも小さくできる場合
→
-IINF
- vに到達不可能な場合 →
引数
N
: 頂点数start
: 始点edges
: 有向辺(in, out, weight)
の集合
戻り値
-
has_negative
: (グラフ全体で)負閉路を含むか -
dist
: 各頂点への最短路 -
prev
: 各頂点の最短路について,その頂点の直前に経由した頂点 -
時間計算量: $
O(NM)
$