ダイクストラ法入門！最短経路問題をゲーム開発で理解しよう

町A（スタート地点）から町D（ゴール）まで移動したい
- 町Aから町Bへの道: 距離4
- 町Aから町Cへの道: 距離2
- 町Bから町Dへの道: 距離3
- 町Cから町Bへの道: 距離1
- 町Cから町Dへの道: 距離5

距離: A=0, B=∞, C=∞, D=∞
未訪問: {A, B, C, D}

Aの隣接地点を更新:
- B: ∞ → 4（A経由）
- C: ∞ → 2（A経由）

訪問済み: {A}
距離: A=0, B=4, C=2, D=∞

Cの隣接地点を更新:
- B: 4 → 3（C経由の方が近い！）
- D: ∞ → 7（C経由）

訪問済み: {A, C}
距離: A=0, B=3, C=2, D=7

Bの隣接地点を更新:
- D: 7 → 6（B経由の方が近い！）

訪問済み: {A, C, B}
距離: A=0, B=3, C=2, D=6

最短距離: 6
最短経路: A → C → B → D

import heapq

def dijkstra(graph, start):
    """
    ダイクストラ法で最短距離を求める関数
    
    Args:
        graph: グラフを表す辞書 {ノード: [(隣接ノード, 距離), ...]}
        start: スタート地点のノード
    
    Returns:
        各ノードへの最短距離を格納した辞書
    """
    # 各ノードへの最短距離を格納（初期値は無限大）
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    # 優先度付きキュー（距離が小さい順に取り出せるリスト）
    # (距離, ノード)のタプルを格納
    priority_queue = [(0, start)]
    
    while priority_queue:
        # 現在の最短距離のノードを取り出す
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # すでに処理済みの場合はスキップ
        if current_distance > distances[current_node]:
            continue
        
        # 隣接ノードを調べる
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            # より短い経路が見つかった場合、距離を更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# グラフの定義（RPGの町の例）
graph = {
    'A': [('B', 4), ('C', 2)],  # 町Aから町Bへは距離4、町Cへは距離2
    'B': [('D', 3)],             # 町Bから町Dへは距離3
    'C': [('B', 1), ('D', 5)],   # 町Cから町Bへは距離1、町Dへは距離5
    'D': []                      # 町D（ゴール）
}

# 実行例
result = dijkstra(graph, 'A')
print("各町への最短距離:")
for node, distance in result.items():
    print(f"町{node}: {distance}")

# 出力:
# 各町への最短距離:
# 町A: 0
# 町B: 3
# 町C: 2
# 町D: 6

if distance < distances[neighbor]:
    distances[neighbor] = distance

distances = {node: float('infinity') for node in graph}

def dijkstra_with_path(graph, start, goal):
    """
    ダイクストラ法で最短距離と経路を求める関数
    
    Returns:
        (最短距離, 経路のリスト)
    """
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    previous_nodes = {node: None for node in graph}  # 経路を記録
    
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # ゴールに到達したら終了
        if current_node == goal:
            break
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node  # 経路を記録
                heapq.heappush(priority_queue, (distance, neighbor))
    
    # 経路を復元
    path = []
    current = goal
    while current is not None:
        path.append(current)
        current = previous_nodes[current]
    path.reverse()
    
    return distances[goal], path

# 実行例
distance, path = dijkstra_with_path(graph, 'A', 'D')
print(f"最短距離: {distance}")
print(f"最短経路: {' → '.join(path)}")

# 出力:
# 最短距離: 6
# 最短経路: A → C → B → D

# ゲームマップの例（0は通行可能、1は壁）
game_map = [
    [0, 0, 1, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

# このマップをグラフに変換してダイクストラ法を適用
# NPCは最短経路でプレイヤーの位置まで移動

例: 道路ネットワーク
- 都市数（ノード）: 1,000
- 道路数（エッジ）: 5,000

配列実装: 約1,000,000回の操作
ヒープ実装: 約80,000回の操作（約12倍高速）