概要

全点対最短経路問題(APSP)を解くアルゴリズム。

グラフ \(G = (V, E)\) の全てのペア \((v, w)\) 間の最短経路コストを求める。

Bellman-Ford Algorithmで一度負辺を除去した上で、Dijkstra’s Algorithmで各頂点からの最短経路を計算する。

計算量

二分ヒープ実装で \(O((|V| + |E|) |V| \log |V|)\)

実装

from collections import deque
from heapq import heappush, heappop

INF = 10**30
def Johnson(G, N):
    h = [0]*N

    update = 1
    for i in range(N):
        update = 0
        for v in range(N):
            d = h[v]
            for w, c in G[v]:
                if c + d < h[w]:
                    h[w] = d + c
                    update = 1
        if not update:
            break
    else:
        return None

    for v in range(N):
        d = h[v]
        g = G[v]
        for j, (w, c) in enumerate(g):
            g[j] = (w, c + d - h[w])

    D = []
    for i in range(N):
        dst = [INF]*N
        dst[i] = 0
        que = [(0, i)]
        while que:
            cost, v = heappop(que)
            if dst[v] < cost:
                continue
            for w, c in G[v]:
                if cost + c < dst[w]:
                    dst[w] = r = cost + c
                    heappush(que, (r, w))
        v = h[i]
        for j in range(N):
            if dst[j] == INF:
                dst[j] = INF
            else:
                dst[j] -= v - h[j]
        D.append(dst)

    return D

Verified

  • AOJ: "GRL_1_C: Shortest Path - All Pairs Shortest Path": source (Python3, 0.20sec)

戻る