Warshall–Floyd

• warshall_floyd(n, edges): 頂点数 $n$ と有向辺のリスト edges = [(u, v, w), ...] から、 $u$ から $v$ への最短距離を d[u][v] とする表を返す。到達できないときは INF（ $= 2^{60}$）。無向グラフなら両向きの辺を入れる
• 負の辺があっても使える。ある $i$ で d[i][i] < 0 なら負閉路がある
• 計算量: $O(N^3)$

コード

INF = 1 << 60


def warshall_floyd(n, edges):
    # edges = [(u, v, w), ...]（有向）
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u, v, w in edges:
        if w < d[u][v]:
            d[u][v] = w
    for k in range(n):
        dk = d[k]
        for i in range(n):
            di = d[i]
            dik = di[k]
            if dik == INF:
                continue
            for j in range(n):
                if dk[j] != INF and dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    return d