令和6年度春期応用技術者試験_午後_問3

r06h_ap_pm3_1.py

def distance():
    N = 5  # ノードの個数
    INF = float("inf")  # 十分大きい定数
    # edge[m, n]には、ノードmからノードnへの距離を格納
    # 二つのノードが隣接していない場合には INF を格納
    edge = [
        [INF, 10, 16, INF, INF],
        [10, INF, 4, 3, INF],
        [16, 4, INF, 2, 3],
        [INF, 3, 2, INF, 6],
        [INF, INF, 3, 6, INF],
    ]
    GOAL = N - 1  # 終点のノード番号
    dist = [INF] * N  # 始点ノード距離。初期値はINF。
    done = [0] * N  # 採点距離が確定したら1を入れる。
    dist[0] = 0
    while True:
        minDist = INF
        for k in range(N):
            if done[k] == 0 and minDist > dist[k]:
                minDist = dist[k]
                curNode = k
        done[curNode] = 1
        if curNode == GOAL:
            return dist[curNode]
        for k in range(N):
            if dist[curNode] + edge[curNode][k] < dist[k] and done[k] == 0:
                dist[k] = dist[curNode] + edge[curNode][k]


print(distance())