アルゴリズム・データ構造図鑑 · 基礎から応用へ

Dijkstra法:非負重みの最短経路を確定する

暫定距離の最小候補を選び、辺の緩和によって最短距離を更新する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 暫定距離と確定した距離を分ける
  2. より短い経路で候補を更新する
  3. 非負という条件が必要な理由
  4. キューの実装と計算量
  5. 古い候補が残る実装を動かす
  6. ゼロ重みと到達不能を区別する
  7. この記事をロゲイアに質問する理解を確かめる

暫定距離と確定した距離を分ける

Dijkstra法は、辺の重みがすべて非負のグラフで、始点から各頂点への最短距離を求めます。始点の距離を0、他を未到達として始め、まだ確定していない頂点のうち暫定距離が最小のものを選びます。その距離を経由して隣へ行く方が短ければ、隣の暫定距離を更新します。この更新を緩和と呼びます。距離の小さい候補を効率よく選ぶために、優先度付きキューを利用できます。

より短い経路で候補を更新する

A→Bが4、A→Cが1、C→Bが2、B→Dが1、C→Dが7とします。Aを処理するとB=4、C=1です。次にCを選ぶとBは1+2=3へ改善され、Dは8になります。続いてB=3を選ぶとDは3+1=4へ改善されます。よってDへの最短経路はA→C→B→Dで距離4です。最初に見つけた候補8を、そのまま答えと決めないことがポイントです。

処理した頂点Bの候補Cの候補Dの候補
A41∞
C318
B314
D314

非負という条件が必要な理由

最小の暫定距離を選んだとき、後からもっと遠い未確定頂点を経由しても、非負の辺を足すだけなら短くならないことが確定の根拠です。負の辺があると、遠いと思っていた経路が後で大幅に短くなる可能性があります。したがって通常のDijkstra法へ負の辺をそのまま与えてはいけません。重み0は非負なので利用できます。負の辺を許す問題ならBellman–Ford法や、DAGに限る別手順などを検討します。

キューの実装と計算量

隣接リストとdecrease-keyを扱う二分ヒープを使う実装では、時間はO((V+E) log V)と評価できます。単純な実装では、距離の更新ごとに新候補を追加し、取り出した候補が現在の距離と違えば古い候補として捨てる方法もあります。この場合はキュー要素数や計算量の細部が変わります。前駆頂点を更新時に記録すれば経路を復元できます。到達不能を示す値、距離加算の整数オーバーフロー、ゼロ重みでの同距離の扱いも確認します。

古い候補が残る実装を動かす

下のPython例は、距離が改善するたびに新しい組をヒープへ追加します。A→B=4、A→C=1、C→B=2なら、Bの距離4の候補を入れた後、Cから3へ改善した候補も入ります。3を処理した後に4が取り出されても、現在の距離と一致しないので捨てます。Bを最初に発見した瞬間に確定済みとすると、この改善を受け入れられません。例では頂点名を比較可能な文字列としています。比較できない状態オブジェクトを同じ優先度でヒープへ入れるなら、連番を補助キーにするなどの工夫も必要です。

Python
from heapq import heappop, heappush

def shortest_paths(graph, start):
    distance = {start: 0}
    heap = [(0, start)]
    while heap:
        cost, u = heappop(heap)
        if cost != distance[u]:
            continue
        for v, weight in graph.get(u, []):
            if weight < 0:
                raise ValueError('nonnegative weights required')
            candidate = cost + weight
            if candidate < distance.get(v, float('inf')):
                distance[v] = candidate
                heappush(heap, (candidate, v))
    return distance

ゼロ重みと到達不能を区別する

非負という条件には0も含まれます。ゼロ重みの辺や閉路があっても、厳密な改善だけで距離を更新すれば、同じ距離の候補を無限に追加する必要はありません。特定のゴールだけを探す場合に早期終了するなら、ゴールを発見した時ではなく、最小の有効な距離で取り出した時点を使います。到達不能な頂点には有限距離を捏造せず、未到達を返します。数値型のオーバーフローやNaNは通常の大小比較を壊すため、入力重みや計算結果の範囲も検証します。経路の復元には改善時の親を別に記録します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ