グラフグラフ, 有向グラフ, 閉路, 最小値, BFS, ベルマンフォード法, ダイクストラ法

アルゴリズム

最小コストの閉路:

任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除く
v から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...

2020年3月7日グラフグラフ, 競プロ, 重み付きグラフ, ベルマンフォード法, 単一始点最短経路, 最短経路, 負の閉路, 負の辺

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、

負の辺が含まれているような場合でも適用 ...