GRL_1の解答例(Python)

単一始点最短経路，単一始点最短経路(負の重みを含む場合)，全点対間最短経路に関する問題です． GRLはグラフ理論に関する問題ですのでこちらの参考書を参考にしました． 本ページでは解答のみの紹介に留めアルゴリズムの解説は行いません． 対応するトピックがどの本の何ページに載っているかや参考になるサイトは適宜紹介します．

1. GRL_1_A: Single Source Shortest Path

# GRL_1_A
import heapq
V,E,r = map(int,input().split())

adjacent_list = [[] for _ in range(V)]
for _ in range(E):
    s,t,w = map(int,input().split())
    adjacent_list[s].append((w,s,t)) # 重みで優先度を付けたいのでwを1番目にする
    
# 始点からの辺を記憶した優先度付きキューを作る
heap = [info for info in adjacent_list[r]]
heapq.heapify(heap)

min_cost = [float("inf") for _ in range(V)]
min_cost[r] = 0
while heap:
    # 重みが小さい順に取り出す
    w,s,t = heapq.heappop(heap)
    # コストが小さくなる場合はコストを更新する
    if min_cost[t] > min_cost[s] + w:
        min_cost[t] = min_cost[s] + w
        # コストが更新されたので先の経路を調べる
        for info in adjacent_list[t]:
            heapq.heappush(heap,info)
        
for m in min_cost:
    if m == float("inf"):
        print("INF")
    else:
        print(m)

2. GRL_1_B: Single Source Shortest Path (Negative Edges)

# GRL_1_B

from collections import deque

def BellmanFord():
    V,E,r = map(int,input().split())

    adjacent_list = [[] for _ in range(V)]
    for _ in range(E):
        s,t,w = map(int,input().split())
        adjacent_list[s].append((w,s,t)) 

    cost_list = [float("inf") for _ in range(V)]
    cost_list[r] = 0
    
    # 各辺に関してV-1回更新できるか確かめる
    for _ in range(V):
        for i in range(V):
            for edge in adjacent_list[i]:
                w,s,t = edge
                if cost_list[t] > cost_list[s] + w:
                    cost_list[t] = cost_list[s] + w
      
    # V回目の更新ができてしまったら負の閉路を含む
    for i in range(V):
        for edge in adjacent_list[i]:
            w,s,t = edge
            if cost_list[s] + w < cost_list[t]:
                # print(cost_list)
                return False

    return cost_list

cost_list = BellmanFord()
if cost_list:
    for c in cost_list:
        if c == float("inf"):
            print("INF")
        else:
            print(c)
else:
    print("NEGATIVE CYCLE")

3. GRL_1_C: All Pairs Shortest Path

# GRL_1_C
def FloydWarshall():
    V,E = map(int,input().split())

    adjacent_array = [[float("inf") for _ in range(V)] for _ in range(V)]
    # 対角成分を0にする
    for i in range(V):
        adjacent_array[i][i] = 0
    
    for _ in range(E):
        s,t,w = map(int,input().split())
        adjacent_array[s][t] = w # 重みで優先度を付けたいのでwを1番目にする
        
    D = adjacent_array
    for k in range(V):
        D_next = [[0 for _ in range(V)] for _ in range(V)]
        for i in range(V):
            for j in range(V):
                # D[i][k]+D[k][j] の方が小さい場合は k を経由すればコストを小さくできる
                D_next[i][j] = min(D[i][j],D[i][k]+D[k][j])
                
        D = D_next[:]
        
    # 負の閉路の長さは高々V以下なので閉路を含まないかをV回更新して確かめる
    for k in range(V):
        D_next = [[0 for _ in range(V)] for _ in range(V)]
        for i in range(V):
            for j in range(V):
                D_next[i][j] = min(D[i][j],D[i][k]+D[k][j])
                # 更新できてしまった場合は閉路を含むのでFalseを返す
                if D[i][j] > D[i][k]+D[k][j]:
                    return False
                
        D = D_next[:]

    D = D_next[:]
        
    return D

ans = FloydWarshall()
if ans:
    for cost_list in ans:
        for i in range(len(cost_list)):
            if i != len(cost_list)-1:
                if cost_list[i] == float("inf"):
                    print("INF",end=" ")
                else:
                    print(cost_list[i],end=" ")
            else:
                if cost_list[i] == float("inf"):
                    print("INF")
                else:
                    print(cost_list[i])
else:
    print("NEGATIVE CYCLE")