ベスパリブ

ベスパもってないです。バイク買いました。

Pythonでダイクストラ法

ダイクストラ法とは

ダイクストラ法とは、「重み付きグラフにおける単一始点最短路アルゴリズム

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

使用条件は以下の通り。

  • 負のコストがないこと
  • 有向グラフ、無向グラフともにOK

ベルマンフォード法より高速なので、負のコストがないならばこちらを使うと良い。

ダイクストラ法の処理の流れは以下のサイトが詳しいです。

algorithmalgorithm

実装と使い方

蟻本に書いてあるとおりのプライオリティキューを使った実装です。

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

参考URL