Dial’s Algorithm

概要

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

コストごとにbucketを用意し、コストが小さい順にbucketに含まれる頂点から探索する。
各bucketでは頂点をDoubly Linked Listで管理し、頂点のコストが更新された時に追加削除を \(O(1)\) でできるようにする。

辺のコストが小さい場合に高速になる。

計算量

グラフ \(G = (V, E)\) に含まれる辺の最大コストを \(W\) とすると \(O(|E| + W |V|)\)

実装

# - N頂点のグラフG
# - 辺の重みは最大W
# - 開始頂点はs
def dial(N, G, W, s):
    B = [-1]*(N*W + 1) # first
    L = [-1]*(N*W + 1) # last

    # prv, nxt: 各頂点の前後を管理
    *prv, = range(-1, N-1)
    *nxt, = range(1, N+1)

    nxt[-1] = -1
    prv[s+1] = s-1
    nxt[s-1] = (s+1 if s < N-1 else -1)
    prv[s] = nxt[s] = -1
    B[0] = L[0] = s
    B[N*W] = +(s == 0)
    L[N*W] = (N-1 if s < N-1 else N-2)

    dist = [N*W] * N
    dist[s] = 0
    for w in range(N*W):
        v = B[w]
        while v != -1:
            for x, c in G[v]:
                e = w + c
                if e < dist[x]:
                    d = dist[x]
                    dist[x] = e

                    # bucket d から 頂点x を削除
                    p = prv[x]; n = nxt[x]
                    if p != -1:
                        nxt[p] = n
                    else:
                        B[d] = n
                    if n != -1:
                        prv[n] = p
                    else:
                        L[d] = p

                    # bucket e の末尾に 頂点x を追加
                    l = L[e]
                    if l != -1:
                        nxt[l] = x
                    else:
                        B[e] = x
                    prv[x] = l; nxt[x] = -1
                    L[e] = x
            v = nxt[v]
    return dist

Verified

  • AOJ: "ALDS1_12_B: Graph I - Single Source Shortest Path I": source (Python3, 0.12sec)

参考

戻る