暫定距離と確定した距離を分ける
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の候補 |
|---|---|---|---|
| A | 4 | 1 | ∞ |
| C | 3 | 1 | 8 |
| B | 3 | 1 | 4 |
| D | 3 | 1 | 4 |
非負という条件が必要な理由
最小の暫定距離を選んだとき、後からもっと遠い未確定頂点を経由しても、非負の辺を足すだけなら短くならないことが確定の根拠です。負の辺があると、遠いと思っていた経路が後で大幅に短くなる可能性があります。したがって通常の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を最初に発見した瞬間に確定済みとすると、この改善を受け入れられません。例では頂点名を比較可能な文字列としています。比較できない状態オブジェクトを同じ優先度でヒープへ入れるなら、連番を補助キーにするなどの工夫も必要です。
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は通常の大小比較を壊すため、入力重みや計算結果の範囲も検証します。経路の復元には改善時の親を別に記録します。