D’Esopo-Pape Algorithm

概要

単一始点最短経路問題(SSSP)を解くアルゴリズム。dequeを用いて計算する。

負辺に対する計算はできるが、負閉路が含まれない必要がある。

大体のケースにおいて、Dijkstra法やBellman-Ford法よりも高速になるらしいが、最悪ケースは指数オーダーになる。

実装

# used[v]: 頂点vの状態
#  0: まだ未計算
#  1: 計算中
#  2: 計算完了 (再計算される可能性あり)

from collections import deque

INF = 10**18
def pape(G, N, s):
    dist = [INF]*N

    used = [0]*N
    used[s] = 1
    dist[s] = 0
    que = deque([s])
    while que:
        v = que.popleft()
        c = dist[v]
        for w, d in G[v]:
            if dist[w] <= c + d:
                continue
            dist[w] = c + d
            if used[w] == 0:
                que.append(w)
                used[w] = 1
            elif used[w] == 2:
                que.appendleft(w)
                used[w] = 1
        used[v] = 2
    return dist

Verified

  • AOJ: "GRL_1_A: Shortest Path - Single Source Shortest Path": source (Python3, 1.51sec)

  • AOJ: "ALDS1_12_C: Graph II - Single Source Shortest Path II": source (Python3, 0.58sec)

参考

戻る