ダイクストラ法とは
グラフ理論の最短経路問題で辺の重みが非負整数のときに用いられる。
具体例
ともかく、具体的に考えてみる。以下のグラフで、AからFへの最短経路を考える。
こちらのグラフをまずPythonで表現しておく。
g = {"A": {"B": 1, "C": 4},
"B": {"A": 1, "C": 2, "D": 5},
"C": {"A": 4, "B": 2, "E": 3},
"D": {"B": 5, "E": 1, "F": 5},
"E": {"C": 3, "D": 1, "F": 1},
"F": {"D": 5, "F": 5}}目標は、頂点Aから始めて、各頂点(B, C, D, E, F)までの最短距離を求めることである。
方法
初期化
まず、各頂点への初期距離を無限大に設定し、始点Aの距離を\(0\)にする。
優先度付きqueの使用
優先度付きqueを使用して、最短距離の頂点を取り出し、その頂点に隣接するすべての頂点の距離を更新する。
Pythonコードの例
def dijkstra(graph, start):
# 初期化
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_vertex = heapq.heappop(pq)
# 現在の距離が記録されている距離より大きい場合はスキップ
if current_distance > distances[current_vertex]:
continue
# 隣接する各頂点の距離を更新
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances一つひとつ解説していく。まず初期化であるが、”inf”あるいは”infinity”で距離をすべて無限大に設定する。
distances = {v: float("inf") for v in g}
print(distances)
{'A': inf, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}始点からの距離は\(0\)とする。
distances[start] = 0最後に、pqを初期化して、現在の距離と、現在の点を入れておく。
pq = [(0, start)]pqが無くなるまで繰り返し
最初のループ
while pq:
current_distance, current_vertex = heapq.heappop(pq)
# current_distance = 0, current_vertex = "A"まず最初に入力した、現在の距離\(0\)と現在地点”A”が出てくる。
if current_distance > distances[current_vertex]:
continue最初の場合、current_distanceは\(0\)で、distances[current_vertex]も\(0\)であるから、このifは無視され、次の指示に移る。
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))ここが肝で、今は点Aにいるので、graph[current_vertex].items()は(“B”: 1)と(“C”: 4)である。まずBの方は、distanceはcurrent_distance(0) + weight(1) = 1となる。distancesは
{'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}であったから、AからBまでのdistance(1)はdistances[neighbor] = infよりも小さい事がわかる。そこで、AからBまでの距離を
distances[neighbor] = distance # 1と更新して、さらにBまでの距離と点Bをpqに入れておく。この時点で、pqは
[(1, "B")]となる。さらに、for loopのCでdistanceはcurrent_distance(0) + weight(4) = 4となる。これももちろん無限大より小さいので、distancesは更新されて、以下のようになる。
{'A': 0, 'B': 1, 'C': 4, 'D': inf, 'E': inf, 'F': inf}これでさらに、pqにCの情報を入れて、1周目のループは終わりになる。
2周目のループ
現時点で、
distances = {'A': 0, 'B': 1, 'C': 4, 'D': inf, 'E': inf, 'F': inf}および
pq = [(1, 'B'), (4, 'C')]となっている。ここから、再度ループを回すと、
current_distance, current_vertex = heapq.heappop(pq) = 1, "B"である。ここでも、if文の条件は満たされないので、次に進む。
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))今はBがcurrent_vertexなので、graphg[current_vertex].items()は
dict_items([('A', 1), ('C', 2), ('D', 5)])である。それぞれについて見てみると、
# A
distance = current_distance + weight = 1 + 1 = 2
# distance < distances[neighbor] (2 < 0)は成り立たない。
# C
distance = current_distance + weight = 1 + 2 = 3
# distance < distances[neighbor] (2 < 4)が成り立つ。
# なので、distances[neighbor] = distanceと更新し、pqにCを入れておく。
# D
distance = current_distance + weight = 1 + 5 = 6
# distance < distances[neigbor] (6 < inf) が成り立つ。
# なので、distances[neighbor] = distanceと更新し、pqにDを入れておく。という感じでどんどん更新を行っていく。
3周目のループ
どんどん続けていく。現時点で、
distances = {'A': 0, 'B': 1, 'C': 3, 'D': 6, 'E': inf, 'F': inf}および
pq = [(4, 'C'), (4, 'C'), (6, 'D')]となっているはずである。ここから、再度ループを回すと、
current_distance, current_vertex = heapq.heappop(pq) = 4, "C"である。ここで、
current_distance > distances[current_vertex] # 4 > 3であるから、Cについては既に最短経路となっており、更新の必要がないことがわかる。
ダイクストラ法
このように、pqが無くなるまでどんどん更新を繰り返し、最終的に最短経路を出力することができる。ちなみに、
if current_distance > distances[current_vertex]:
continueの部分はなくても問題なく最短経路が求められることが上の過程からもわかる。
関連記事
Python3による二分探索、三分探索の方法
Bron–Kerbosch algorithm ブロン・カーボッシュアルゴリズム
コメント