ベスパリブ

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

Pythonでダイクストラ法

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

編集履歴

(2021/02/21)ダイクストラのプライオリティキューが最短距離の小さい順に取り出されるようになっていなかったので、それを修正

ダイクストラ法とは

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

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

使用条件は以下の通り。

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

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

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

algorithmalgorithm

実装と使い方

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

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

参考URL