tooh’s diary

半角全角、常体敬体が入り乱れるカオス

2019-07-01から1日間の記事一覧

ベルマンフォード法

ある一点からスタートし、そこから残りの全ての頂点に達するのに必要な最短コストを計算するときに使える。計算量は、頂点V、辺の数EとしてO(VE)。負の辺があっても使えるのが、ダイクストラ法と違うところ(強み)。構造は単純で、頂点の数vから1引いた数だ…