ダイクストラ法(1959)
最短経路を探索するための古典的・代表的手法。
Dijkstraの速度は、優先キューの実装の仕方に懸かってくる。(単純故それくらいしかいじるところが無いとも言えるし、いじったところで滅茶苦茶速くはならない)
Pythonなどの遅い言語で、標準ライブラリにヒープが実装されている場合は、下手に自力実装するより素直にそれを使おう。
[set() for _ in range(n)]
)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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' ) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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(など、同一の値)に限られる場合は、BFS(幅優先探索、Breadth First Search)が使える。
双方向キュー(両端キュー、deque)を用いる。これは先頭からの取り出し・末尾への追加がいずれも高速に行えるデータ構造である。
「先頭から取り出して末尾に追加」を繰り返すと、先頭の値が常にその中で最小の値に保たれる。
また、BFSの場合は「一度キューに追加された頂点は、後から別の経路でより小さいコストでたどり着く方法が見つかることは無い」ので、 1つの頂点がキューに追加されるのは必ず一度きりとなる。
計算量は O(|E|+|V|) となる。
0-1 BFSが使える。
双方向キューを使うのはBFSと一緒。
先頭の値を常に最小値に保つようにするため、以下のようにする。
計算量は O(|E|+|V|) となる。
BFSとは言いつつ、使うデータ構造が双方向キューなだけで “Breadth First” ではないので少しややこしいネーミングかもしれない。
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 で割ったあまりの番号のリストに入れる」としておくとうまくいく。