【Python】グラフのノード間の最短経路を求めるアルゴリズム
令和6年度 春期 応用情報技術者試験 午後 問3 で出題された「グラフのノード間の最短経路を求めるアルゴリズム」（ダイクストラ法）を Python で実装してみます。
下図にノードが五つのグラフの例を示します。
図の例では，始点を V1 ノードとし，終点を V5 のノードとした場合の最短経路は，V1，V2，V3，V5 のノードを順にたどる経路となります。
始点から終点までの最短経路を求める手順
ダイクストラ法による始点から終点までの最短距離の算出は次のように行う。
最初に，各ノードについて，始点からそのノードまでの距離（以下，始点ノード距離という）を作業用に導入して十分に大きい定数としておく。ただし，始点の始点ノード距離は 0 とする。この時点では，どのノードの最短距離も確定していない。
次に，終点の最短距離が確定するまで，1. ～ 3. を繰り返す。ここで，始点との距離を算出する基準となるノードを更新起点ノードという。
- 最短距離が確定していないノードの中で，始点ノード距離が最小のノードを更新起点ノードとして選び，そのときの始点ノード距離の値で，当該更新起点ノードの最短距離を確定する。更新起点ノードを選ぶ際に，始点ノード距離が最小となるノードが複数ある場合は，その中の任意のノードを更新起点ノードとして選ぶ。
- 更新起点ノードが終点であれば，終了する。
- 1. で選択した更新起点ノードに隣接しており，かつ，最短距離が確定していない全てのノードについて，更新起点ノードを経由した場合の始点ノード距離を計算する。ここで計算した始点ノード距離が，そのノードの現在までの始点ノード距離よりも小さい場合には，そのノードの現在までの始点ノード距離を更新する。
ダイクストラ法の Python コード
始点から終点までの最短距離を求めるダイクストラ法の Python コードを示します。
import heapq
def dijkstra(graph, start, end):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
previous_nodes = {node: None for node in graph}
queue = [(0, start)]
while queue:
current_distance, current_node = heapq.heappop(queue)
if distances[current_node] < current_distance:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node
heapq.heappush(queue, (distance, neighbor))
path = []
while end:
path.append(end)
end = previous_nodes[end]
path.reverse() # Reverse to get path from start to end
return distances, path
# グラフの定義
graph = {
'V1': {'V2': 10, 'V3': 16},
'V2': {'V1': 10, 'V3': 4, 'V4': 3},
'V3': {'V1': 16, 'V2': 4, 'V4': 2, 'V5':3},
'V4': {'V2': 3, 'V3': 2, 'V5':6},
'V5': {'V3':3, 'V4':6}
}
distances, path = dijkstra(graph, 'V1', 'V5')
print("最短距離 : ", distances['V5'])
print("最短経路 : ", "->".join(path))上記の Python コードを実行した結果は，以下のように出力されます。
最短距離 : 17
最短経路 : V1->V2->V3->V5ノード V1 からノード V5 までの最短距離は 17，最短経路は V1，V2，V3，V5 となり，グラフのノード間の最短経路を求めるアルゴリズムが実装されていることがわかります。
参考文献
- 令和6年度 春期 応用情報技術者試験 午後 問題 問3「グラフのノード間の最短経路を求めるアルゴリズム」
- 午後問題対策 プログラミング｜目指せ！応用情報技術者
- 【実例で学ぶ】Pythonで実装する最もシンプルなダイクストラ法
更新履歴
- 2024年10月15日 新規作成
