Dijkstra

ダイクストラ法(1959)

最短経路を探索するための古典的・代表的手法。

制約

リンクコストは非負

優先キュー

Dijkstraの速度は、優先キューの実装の仕方に懸かってくる。（単純故それくらいしかいじるところが無いとも言えるし、いじったところで滅茶苦茶速くはならない）

優先度付きキュー
- 値を優先度付きで管理するキュー
- 「要素の追加」と「優先度最大の要素の取り出し」の操作ができる
- 追加や取り出しを繰り返しても、次の優先度最大の要素が常に高速に取り出せるよう工夫されている
- ヒープというデータ構造で実装することが多い

二分ヒープ
- 単純明快で実装も簡単なヒープ
- 単純さ故、オーダー記法上では他のヒープに劣るものの、実装してみたら一番速かった、なんてこともある
フィボナッチヒープ
- 木を複数に分けることで、更新を怠惰にすることができ、追加・削除が速くなる
- ただ、木の組み替えが必要になったタイミングで、たまに遅くなる
基数ヒープ
- radix-heap/README_ja.md at master · iwiwi/radix-heap
- 単調順位キュー（追加する値は、最後に取り出した値より大きくなくてはならないという制約がある）
  - Dijkstraで使用する場合はその制約を満たす

Pythonなどの遅い言語で、標準ライブラリにヒープが実装されている場合は、下手に自力実装するより素直にそれを使おう。

実装例

Python3

ノードは0～N-1のN個
リンクは、N個のsetを持った配列（[set() for _ in range(n)]）
- ノードkのリンク情報は、links[k]
- 各setには、リンクを示すtupleを(コスト, ノードID)の形で格納

経路復元不要（距離のみ）

from heapq import heappush, heappop, heapify

def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float('inf')

経路復元可

from heapq import heappush, heappop, heapify


def trace(s, t, ancestors):
    route = [t]
    c = t
    while True:
        a = ancestors[c]
        assert a is not None, 'Failed to trace'
        route.append(a)
        if a == s:
            break
        c = ancestors[c]
    route.reverse()
    return route


def dijkstra(s, t, links):
    heap = [(*l, s) for l in links[s]]
    heapify(heap)
    visited = set()
    ancestors = [None] * n
    while heap:
        cost, node, ancestor = heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        ancestors[node] = ancestor
        if node == t:
            return cost, trace(s, t, ancestors)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2, node))
    return float('inf'), None

制約がある場合の高速化

Dijkstraは「コストが暫定コストのまま未確定の頂点の中で、その時点で最も暫定コストの小さい頂点は、それを最短コストとして確定できる」というのが本質。

その上で、辺のコストに一定の制約がある場合は「最もコストの小さい未確定頂点を見つけて取り出す」作業を、優先キューより高速に実現できる。

辺のコストが全て「1」

辺のコストが全て1（など、同一の値）に限られる場合は、BFS（幅優先探索、Breadth First Search）が使える。

双方向キュー（両端キュー、deque）を用いる。これは先頭からの取り出し・末尾への追加がいずれも高速に行えるデータ構造である。

両端キュー

「先頭から取り出して末尾に追加」を繰り返すと、先頭の値が常にその中で最小の値に保たれる。

また、BFSの場合は「一度キューに追加された頂点は、後から別の経路でより小さいコストでたどり着く方法が見つかることは無い」ので、 1つの頂点がキューに追加されるのは必ず一度きりとなる。

計算量は $O(|E| + |V|)$ となる。

辺のコストが全て「0」か「1」

0-1 BFSが使える。

双方向キューを使うのはBFSと一緒。

先頭の値を常に最小値に保つようにするため、以下のようにする。

0の辺を伝って新しい頂点を追加（またはコストの更新）する場合は先頭に追加
1の辺を伝って新しい頂点を追加する場合は末尾に追加

01-BFSのちょっと丁寧な解説 - ARMERIA

計算量は $O(|E| + |V|)$ となる。

BFSとは言いつつ、使うデータ構造が双方向キューなだけで “Breadth First” ではないので少しややこしいネーミングかもしれない。

辺のコストが0以上 $K$ 以下の整数

$K$ が10とか100とか、頂点や辺数に比べて十分小さい場合、Dial's Algorithm と呼ばれるものが使える。

要素を追加削除できるリストを $K+1$ 個用意する。優先キューや両端キューのように凝ったデータ構造でなくてよい。

辺のコストが $0～K$ のとき、仮にDijkstraで探索を行った場合を考えると、優先キューに入っている頂点の暫定コストは、どの時点においても「その時点での最小コスト～その時点での最小コスト $ + K$」の $K+1$ 種類しかない。

よって、「暫定コストが0の頂点用リスト」「1の頂点用リスト」……「$K$ の頂点用リスト」の $K+1$ 個のリストを用意しておき、優先キューの代わりに、どのリストに入れるかで大小の順番を管理する。

小さい方のリストから頂点を取り出していくと、常に「その時点での最小」を処理できることになる。

「暫定コストが0の頂点用リスト」を空にして「1の頂点用リスト」を処理するようになったら、今度はコストの範囲が $1～K+1$ になりうるので、「0の頂点用リスト」として使っていたものをローテーションして「$K+1$ の頂点用リスト」として使うようにする。

これは、リストに $0～K$ の番号を振り「コストを $K+1$ で割ったあまりの番号のリストに入れる」としておくとうまくいく。

目次