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

アルゴリズム

最小コストの閉路:

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

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

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

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

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