[[Dijkstra]]

Dijkstra

ダイクストラ法(1959)

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

制約

  • リンクコストは非負

優先キュー

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

programming_algorithm/route_search/dijkstra.txt · 最終更新: 2017/10/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0