【最短経路問題】ダイクストラ法の計算コスト！ポケモンGOのジムバトル最短討伐時間を題材に確認しました！

import sys

def dijkstra(graph, start):
    # ノード数
    num_nodes = len(graph)
    
    # 初期化
    distances = [sys.maxsize] * num_nodes  # 各ノードまでの最短コスト
    visited = [False] * num_nodes  # ノードの訪問状態
    distances[start] = 0  # スタートノードの距離は0
    parent = [-1] * num_nodes  # 最短経路木における各ノードの親ノード
    
    for _ in range(num_nodes):
        # 未訪問のノードの中で最短コストのノードを選択
        min_distance = sys.maxsize
        min_node = -1
        for i in range(num_nodes):
            if not visited[i] and distances[i] < min_distance:
                min_distance = distances[i]
                min_node = i
        
        # 選択したノードを訪問済みとする
        visited[min_node] = True
        
        # 選択したノードからの移動先のコストを更新
        for i in range(num_nodes):
            if (not visited[i]) and graph[min_node][i] != float('inf'):
                new_distance = distances[min_node] + graph[min_node][i]
                if new_distance < distances[i]:
                    distances[i] = new_distance
                    parent[i] = min_node
    
    # 最短経路上のノードを取得
    path = []
    node = num_nodes - 1  # ゴールノードから逆にたどる
    while node != -1:  # スタートノードに到達するまで親ノードをたどる
        path.append(node+1)
        node = parent[node]
    
    path.reverse()  # スタートからゴールまでの順序にする
    
    return distances, path

# 隣接行列を作成
graph = [[0, 30, 60, float('inf'), float('inf'), float('inf')],
         [float('inf'), 0, float('inf'), 40, 17+3, float('inf')],
         [float('inf'), float('inf'), 0, 40+3, 17, float('inf')],
         [float('inf'), float('inf'), float('inf'), 0, float('inf'), 0],
         [float('inf'), float('inf'), float('inf'), float('inf'), 0, 0],
         [float('inf'), float('inf'), float('inf'), float('inf'), float('inf'), 0]]

start_node = 0  # スタートノード
target_node = 5  # ゴールノード

distances, path = dijkstra(graph, start_node)

# スタートノードからゴールノードまでの最短コストを表示
print("最短コスト:", distances[target_node])

# スタートノードからゴールノードまでの最短経路を表示
print("最短経路:", "->".join(str(node) for node in path))