Shortest Path Faster Algorithm (SPFA)

概要

単一始点最短経路問題(SSSP)を解くアルゴリズム。

重み付きグラフ \(G = (V, E)\) の始点 \(v_s\) から各頂点 \(v_t\) への最短距離を求める。
辺のコストに負が含まれていても正しく動き、負閉路も検出することができる。

ベルマンフォード法よりも高速に動作することが期待できる。

計算量

\(O(|V||E|)\)

実装

Small Label First を用いた実装

from collections import deque

INF = 10**18
# 返り値:
#  None (負閉路が存在した場合)
#  List[int] (それ以外)
def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0]* N

    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = c + d
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and c + d < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
    return dist

Verified

  • AOJ: "GRL_1_B: Shortest Path - Single Source Shortest Path (Negative Edges)": source (Python3, 0.03sec)

参考

戻る