ダイクストラ法（Dijkstra’s algorithm）とは
ダイクストラ法とは、
です。
最小経路とはスタートからゴールまでに通るパスの和が最小になるもののことです。
以下の例では、AからFまでの最短経路はA→D→E→B→C→Fとなります。
ただし、ダイクストラ法では負の重みをもつグラフには適用できない点に注意が必要です。
重みをもつグラフに対しては、ベルマンフォードのアルゴリズムやワーシャルフロイドのアルゴリズム等を適用することができます。
アルゴリズムの概要
1. 初期化
スタート地点を設定し、スタートから各頂点への距離を無限大（∞）に設定します。
ただし、スタート自身の距離は0とします。
2. 隣接ノードの距離を更新
未確定の頂点の中から、現在の最短距離が最小の頂点を選択します。
その頂点を確定済みにして、隣接する頂点の距離を更新します。
更新する距離の計算は、
で計算し、これが既存の距離よりも小さい場合に更新します。
3. 繰り返し
「2. 隣接ノードの距離を更新」を繰り返します。
全ての頂点が確定するか、更新する必要がなくなれば終了します。
実装(Python)
ダイクストラ法をpythonで実装した例です。
from heapq import heappush, heappop
def dijkstra(graph, start):
INF = float("inf")
distances = {node: INF for node in graph}
distances[start] = 0
min_heap = [(0, start)]
while min_heap:
current_distance, current_node = heappop(min_heap)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heappush(min_heap, (distance, neighbor))
return distances実行してみます。
graph = {
'A': {'B': 20, 'D': 5},
'B': {'A': 20, 'C': 10, 'E': 3},
'C': {'B': 10, 'F': 7},
'D': {'A': 5, 'E': 10},
'E': {'B': 3, 'D': 10, 'F': 25},
'F': {'C': 7, 'E': 25},
}
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(shortest_paths){'A': 0, 'B': 18, 'C': 28, 'D': 5, 'E': 15, 'F': 35}
参考文献
コメント