組合せとグラフの理論（塩田）第8回 (2)　最短路問題
前へ / 戻る / 次へ

問題設定

Def.3　重み付きグラフ $G$ 内の歩道や部分グラフに対して、 それが含む辺の重みの合計を、 その歩道や部分グラフの重みと定める。
最短路問題　連結な重み付きグラフ $G$ において、 出発点 $S$ と到着点 $T$ を指定したとき、 重み最小の $S$-$T$道を求めよ。
※　重みが距離の場合がまさしく最短路ですので、それにちなんだネイミングです。

欲張りアルゴリズムは NG

Rem.4　目先の利益しか考えない「欲張りアルゴリズム」では最短路問題は解けない。
　次のグラフで欲張りさんが最短の $S$-$T$ 道を探すとしましょう。
出発点 $S$ から直接見えるのは $U$, $V$, $W$ で、 このうち一番近い $U$ へ進みます。
$U$ から直接見えるのは $S$, $V$, $T$ で、 $S$ へ戻っては意味が無いので、 $V$ と $T$ の近い方の $V$ へ進みます。
$V$ からは全ての頂点が見えていて、 $S$ や $U$ へは戻らないので、 $W$ と $T$ の近い方の $T$ へ進み、ゴールします。
しかし本当の最短路は $S \rightarrow W \rightarrow T$ ですから、 欲張りさんのアルゴリズムでは見つけられません。

ダイクストラ法

　最短路問題には決定版のアルゴリズムがあります。
Algorithm 5（ダイクストラ法）
  • 入力：連結な重み付きグラフ $G$ と、出発点 $S$、到着点 $T$
  • 出力：最短の $S$-$T$ 道
  1. 全ての頂点 $v$ に仮ラベル $\ell(v)$ を発行する。
    • 出発点は $\ell(S)=0$
    • $S$ 以外の頂点 $v$ は $\ell(v)=\infty$
  2. 親を覚えるためのリストを宣言する。
  3. 仮ラベルが最小のものを永久ラベルに昇格させる。 ただし候補が複数あるときは、番号（アスキーコード、アルファベット順 etc.）が一番小さいもののみ昇格させる。
  4. $\ell(T)$ が永久ラベルに昇格したら、$T$ から逆順に親をたどって $S$-$T$ 路を出力し終了する：
    $S$ $\rightarrow$ $\cdots$ $\rightarrow$ ($T$ の親の親) $\rightarrow$ ($T$ の親) $\rightarrow$ $T$
  5. 今昇格した頂点 $x$ の全ての未昇格な隣接点 $v$ 全てに対し、
    $\ell(x)+w(xv) \lt \ell(v)$
    であれば
    $\ell(v)$ $\leftarrow \ell(x)+w(xv)$, $\quad$ ( $v$ の親 ) $\leftarrow x$
    と更新する。
  6. 3°に戻る。
　永久ラベルは確定した最短距離を表していて、ステップ 5°は、
  • $\ell(x)+w(xv)$ $=$ (確定した最短の $S$-$x$ 道と辺 $xv$ を経て $v$ に至る道の距離)
  • $\ell(v)$ $=$ (今まで見つかっている最短の $S$-$v$ 道の距離)
を比較しています。

実行例

Ex.6　次のグラフでダイクストラ法を実行し、$A$ から $F$ への最短路を求めてみましょう。
　以下、永久ラベルには〇を付け、永久ラベルに昇格したばかりの頂点を青色で示すことにします。 また、最初の仮ラベル $\infty$ は省略し、 親子関係は赤い線で示しています。

まず出発点の $\ell(A)$ を永久ラベルに昇格させます。
$A$ の隣接点 $B$, $D$, $E$ の仮ラベルを、$A$ からの距離 3, 3, 7 に更新します。
仮ラベル 3 の頂点のうち、アルファベット順で若い方の $\ell(B)$ を永久ラベルに昇格させます。
$B$ の未昇格な隣接点の仮ラベルを 5°に従って更新します。 特に $E$ は $B$ を経由したルートの方が短いので仮ラベルが 7 から 5 に減ります。
最小の仮ラベル $\ell(D)$ を永久ラベルに昇格させます。
$D$ の未昇格な隣接点は $E$ のみですが、 $D$ を経由しても近くならないので仮ラベルは更新されません。
最小の仮ラベル $\ell(E)$ を永久ラベルに昇格させます。
$C$ は $E$ を経由したルートの方が短いので仮ラベルが 8 から 6 に減ります。
最小の仮ラベル $\ell(C)$ を永久ラベルに昇格させます。
$F$ は $C$ を経由したルートの方が短いので仮ラベルが 10 から 9 に減ります。
到着点の $\ell(F)$ が永久ラベルに昇格して終了します。 最短路は $A$ $\rightarrow$ $B$ $\rightarrow$ $E$ $\rightarrow$ $C$ $\rightarrow$ $F$ となりました。
※　慣れてくれば、グラフの絵ひとつにラベルを書くだけで作業できるようになります。
Prop.7　全ての辺の重みが 1 であれば、ダイクストラ法は幅優先探索（到着点が探索されるまで）に等しい。
　「永久ラベルに昇格した頂点」が幅優先探索の探索点に当たり、 $\ell(v)$ が $\infty$ から更新された瞬間に $v$ はキューに登録されます。

前へ / 戻る / 次へ