Dijkstra法による最短経路探索
非負の辺の重みを使って、暫定距離が更新され最短距離として確定する過程を学びます。
説明
最短経路では、通過する辺の重みの合計を最小にします。Dijkstra法は未確定頂点のうち暫定距離が最小のものを選び、その頂点から出る辺で他の距離を更新します。全ての辺が非負という条件で、選んだ距離を確定できます。
AからBへ4、Cへ1、CからBへ2、BからDへ1、CからDへ5というグラフを使います。直接の経路より短い迂回路が見つかる更新を追い、最後に辺の重みを変えて最短経路が変わることを確かめます。
1距離表の初期値
開始点Aは0、それ以外はまだ経路が見つかっていないため無限大です。prevには最短候補の一つ前の頂点を記録します。
graph = {'A': {'B': 4, 'C': 1}, 'B': {'D': 1}, 'C': {'B': 2, 'D': 5}, 'D': {}}辺と非負の重み; distance = {v: float('inf') for v in graph}; distance['A'] = 0距離を初期化; prev = {}; fixed = set()前頂点と確定済み; distance初期距離表未到達の無限大と、大きいが有限の距離は別です。最初に選ぶAの距離0だけが既知です。
2Aを確定して隣を更新
Aから直接到達するBとCに距離4と1を記録します。新しい候補が現在値より小さいとき距離を更新する操作を緩和と呼びます。
fixed.add('A')Aを確定; distance['B'] = 4; distance['C'] = 1Aからの候補; prev.update({'B': 'A', 'C': 'A'})候補経路の前頂点; distance, prev距離と経路Bの4とCの1はまだ暫定値です。直接辺で到達できたことだけでは最短と断定できません。次に未確定で最小のCを選びます。
3C経由でBを短縮
未確定最小はCの1です。CからBなら1+2=3、Dなら1+5=6となります。
current = min((v for v in graph if v not in fixed), key=distance.get)未確定の最小距離を選択; candidates = {v: distance[current]+weight for v, weight in graph[current].items()}C経由の候補距離; current, candidates選んだ頂点と候補Bへの候補3は現在の4より短く、Dへの候補6も無限大より短い値です。どちらも更新対象になります。
4経路上の直前の頂点も変更する
距離だけでなく、その距離を実現する前頂点もCへ変更します。
fixed.add(current)Cを確定; distance.update(candidates)改善した距離を保存; prev.update({v: current for v in candidates})前頂点もCへ; distance, prev, sorted(fixed)更新後の状態Bの前頂点はAからCになりました。A→C→Bは距離3です。DはC経由の6ですが、まだ未確定なので後の更新を受けます。この例では両候補とも改善することを確認した上でupdateしています。
5B経由でDを短縮
次の最小はBの3です。BからDの重みは1なので、Dへの候補は4になります。
current = min((v for v in graph if v not in fixed), key=distance.get)Bを選択; candidate = distance[current] + graph[current]['D']B経由の距離; candidate, distance['D'], candidate < distance['D']現在値と比較候補4は現在の6より短いため、Dを更新します。最初にDへ到達したC経由の候補より、後で見つかったB経由の候補が短い例です。
6Dを確定して経路を復元
Bを確定しDの距離と前頂点を更新します。残るDを確定した後、前頂点を逆にたどります。
fixed.add('B'); distance['D'] = candidate; prev['D'] = 'B'; fixed.add('D')BとDの確定; route = ['D']終点から開始; route.insert(0, prev[route[0]]); route.insert(0, prev[route[0]]); route.insert(0, prev[route[0]])前頂点を3回たどる; distance, route距離と復元経路最短経路はA→C→B→D、合計1+2+1=4です。距離表と前頂点の両方を保持すると、最短値だけでなく経路も得られます。
7重みを変えて候補経路を比較
C→Bを2から8へ変えます。この小さなグラフでAからDへ進む経路は3通りなので、各合計を直接計算して比較できます。
graph['C']['B'] = 8辺の重みを変更; costs = {'A-B-D': graph['A']['B']+graph['B']['D'], 'A-C-D': graph['A']['C']+graph['C']['D'], 'A-C-B-D': graph['A']['C']+graph['C']['B']+graph['B']['D']}3経路の合計; costs, min(costs, key=costs.get)変更後の最短経路最短はA→B→Dの5へ変わりました。以前の距離表4は古い重みに対する結果なので、変更後に使い回すことはできません。ここでは全経路の列挙で変更後の答えを検算しました。
8負の重みを持つ辺があると最短距離を確定できない
別の3頂点でA→Bが2、A→Cが5、C→Bが-4だとします。Bを2で先に確定しても、後からC経由の1が見つかります。
direct = 2Bへの直接距離; via_c = 5 + (-4)負の辺を経由; direct, via_c, via_c < direct先に確定した値より短くなるCの暫定距離5がBの2より大きくても、その先の負の辺で合計が1に下がります。Dijkstra法で最小の未確定距離を確定できる根拠は、後続の非負辺で距離が小さくならないことです。負の辺を扱う場合は別の方法が必要です。
まとめ
暫定距離は経路が見つかるたびに改善でき、到達しただけでは確定しません。
非負の辺では未確定の最小距離を確定し、そこからの候補で他の距離を更新できます。
前頂点から経路を復元できます。重みの変更や負の辺は、既存の距離表や確定条件に影響します。
操作履歴と解説を振り返れます。
Python 3
graph = {'A': {'B': 4, 'C': 1}, 'B': {'D': 1}, 'C': {'B': 2, 'D': 5}, 'D': {}}; distance = {v: float('inf') for v in graph}; distance['A'] = 0; prev = {}; fixed = set(); distance{'A': 0, 'B': inf, 'C': inf, 'D': inf}fixed.add('A'); distance['B'] = 4; distance['C'] = 1; prev.update({'B': 'A', 'C': 'A'}); distance, prev({'A': 0, 'B': 4, 'C': 1, 'D': inf}, {'B': 'A', 'C': 'A'})current = min((v for v in graph if v not in fixed), key=distance.get); candidates = {v: distance[current]+weight for v, weight in graph[current].items()}; current, candidates('C', {'B': 3, 'D': 6})fixed.add(current); distance.update(candidates); prev.update({v: current for v in candidates}); distance, prev, sorted(fixed)({'A': 0, 'B': 3, 'C': 1, 'D': 6}, {'B': 'C', 'C': 'A', 'D': 'C'}, ['A', 'C'])current = min((v for v in graph if v not in fixed), key=distance.get); candidate = distance[current] + graph[current]['D']; candidate, distance['D'], candidate < distance['D'](4, 6, True)
fixed.add('B'); distance['D'] = candidate; prev['D'] = 'B'; fixed.add('D'); route = ['D']; route.insert(0, prev[route[0]]); route.insert(0, prev[route[0]]); route.insert(0, prev[route[0]]); distance, route({'A': 0, 'B': 3, 'C': 1, 'D': 4}, ['A', 'C', 'B', 'D'])graph['C']['B'] = 8; costs = {'A-B-D': graph['A']['B']+graph['B']['D'], 'A-C-D': graph['A']['C']+graph['C']['D'], 'A-C-B-D': graph['A']['C']+graph['C']['B']+graph['B']['D']}; costs, min(costs, key=costs.get)({'A-B-D': 5, 'A-C-D': 6, 'A-C-B-D': 10}, 'A-B-D')direct = 2; via_c = 5 + (-4); direct, via_c, via_c < direct(2, 1, True)
演習完了