ダイクストラ法をPyhtonで書く！

皆さん、こんにちは！

ハリーです。今回は先週の続きでダイクストラ法をやっていきたいと思います。今回のテーマとしては、前回やったダイクストラ法を Python で書いていきたいと思います。それではやっていきましょう～！

ダイクストラ法

ダイクストラ法とは、グラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年にEdsger Dijkstra氏 によって考案されました。

Pythonでの実装

まず、ダイクストラ法を実装するにあたって、ヒープキューを使用します。（ヒープキューとは、要素の追加と最小の要素の取り出しをそれぞれ $O(log N)$ で実行できるデータ構造です）

初めに、heapq モジュールをインポートします。

from heapq import heappush, heappop

次に、始点とノード数を受け取ります。

def dijkstra(s, n):

合計距離を保存するための配列 dist 、距離とノードを入れるための配列 hq 、ノードが確定済みか確認するための配列 check を準備します。

dist = [INF] * n

hq = [(0, s)]

dist[s] = 0

check = [False] * n

では、ダイクストラ法の手順で処理を行います。

1. 今いるノードを取り出します。

2. 訪問済みの True を入れます。

3. if 文で、訪問済みではない、かつ暫定距離より短いかどうかを判定します。

4. 3 の条件に当てはまる場合、距離を更新します。

5. これを繰り返していきます。

while hq:

  v = heappop(hq)[1]

  check[v] = True

  for to, cost in graph[v]:

      if check[to] == False and dist[v] + cost < dist[to]:

          dist[to] = dist[v] + cost

          heappush(hq, (dist[to], to))

return dist

おわりに

　いかがだったでしょうか？初めてのダイクストラ法でしたが、個人的には BFS (幅優先探索) よりややこしように感じました。まだまだ理解が足りていませんが、これからいろいろな問題を解いて慣れていこうと思います。これで、私のライブラリが 3つになりました！もっと増やしていきたいですね。来週はテスト週間なのでお休みさせてください！留年をかけた勝負をしてきます....。

それでは、皆さんまた再来週！