ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

Pythonでベルマンフォード法

Python3 競技プログラミング アルゴリズム

ベルマンフォード法とは

蟻本によれば、「重み付き有向グラフにおける単一始点最短路アルゴリズム」

つまり、「始点s から各頂点i までの最短コストを求める」アルゴリズムです。

以下の条件で使えます。

  • DAG（有向グラフで閉路を持たない）である
  • 負のコストがあってもOK

すべての辺のコストが非負の場合、ダイクストラ法を使ったほうが高速に最短路が求まります。

実装と使用例

辺の数を E、頂点の数を Vとすると、計算量は O( EV )

実行結果

---sample1---
bf.exist_negatve_loop(): False
path: [0, 5, 3, 5, 4, 7]
---sample2---
bf.exist_negatve_loop(): True
---sample3---
bf.exist_negatve_loop(): True

参考URL

ベルマンフォード法の動きは、以下のリンク先が詳しいです。

Algorithm