bellman_ford.hpp ファイル

#include "../../../kyopro_library/template.hpp"

[ソースコード]

関数
pair< bool, vector< ll > >	BellmanFord (const vector< vector< pair< int, ll > > > &g, int start)
	ベルマンフォード法

関数詳解

BellmanFord()

pair< bool, vector< ll > > BellmanFord	(	const vector< vector< pair< int, ll > > > &	g,
		int	start )

ベルマンフォード法

負の閉路が存在するか否かの bool 値と、各頂点までの最短距離を記録した配列の組を返す

覚え書き

O(VE)

注意

負閉路が存在する場合、最短経路が正しく計算されない場合がある。 このときは逆辺を張ったグラフで BFS 等を行い、目的の終点から到達可能である頂点を列挙し、 そのような頂点のみでベルマンフォード法を実行して調べる必要がある。 https://yukicoder.me/submissions/967952 https://mhrb-minase.hatenablog.com/entry/2019/08/20/003915

bellman_ford.hpp の 14 行目に定義があります。