数弱によるダイクストラ法証明

はじめに

大学の学部の授業でダイクストラ法を習った時、同時に証明も一通り習いましたが帰納法と背理法を同時に扱ったりしていて数弱情報系の自分にはてんてこまいでした。
京大院試に向けて一通り復習している中でようやく腑に落ちたのでここにまとめておきます。
なお、この記事全体は記事末尾に記載した参考文献に基づいております。

ダイクストラ法

ダイクストラ法はグラフ$G=(V,E)$のなかで始点$v_s\in V$と終点$v_t\in V$を繋ぐ経路のうち最短となる経路を求めるアルゴリズムです。
ダイクストラ法のアルゴリズムについては参考文献[データ構造とアルゴリズム]より

d(v_s)\leftarrow 0 \
V-{v_s}に属す全ての頂点vに対してd(v)\leftarrow \infty \
A \leftarrow {v_s }\
----以下繰り返しステップ----\
Aの中の頂点のうちdの値が最小となっているvを取り出す\
v=v_tならd(v_t)を出力して終了\
T(v)に属す各頂点wに対して\
if d(w) = \infty\ then\ w をAに追加してd(w)\leftarrow d(w) + l(v, w)\
elseif\ d(w) > d(v) + l(v, w)\ then\ d(w) \leftarrow d(v) + l(v, w)

ここで$d(v)$は$v_s\rightarrow v$のそのステップにおける最短距離, $T(v)$は$v$に隣接する頂点集合です。このアルゴリズムが言いたいことは、$d$が最小となっているものをとり出し、そこから行ける頂点に対して取り出した頂点から行った場合、より短い経路で行ける時にはその行先の最短距離を更新する。そしてそれを繰り返し、$d$が最短のものとして,終点である$v_t$が取り出された場合にはその$d(v_t)$が$v_s\rightarrow \ v_t$への最短距離となっている、ということです。（と自分は理解しています。）

## ダイクストラ法の証明
上の説明の中で
>$d$が最短のものとして,終点である$v_t$が取り出された場合にはその$d(v_t)$が最短経路となっている

と説明しましたが本当にそう言えるのでしょうか？
これは以下に示す定理を証明することで示せます。
### 定理
ダイクストラ法のアルゴリズムの中で$A$から取り出された任意の頂点$v$に対してその時点での$d(v)$は$v_s$から$v$までの最短距離となっている

### この定理を示したい気持ち
任意のタイミングで取り出された$v$の$d(v)$が最短距離であることを示せれば最後に$v_t$が取り出された時の$d(v_t)$が最短距離であると言えるからですね

### 証明
全体の証明は帰納法を用います。
そのために$k-1$回目までに取り出された頂点$v'$については
その時点における$d(v')$はスタートからの最短距離になっていると仮定します。
次に帰納法による証明のために
$k$回目に取り出された$v$について$d(v)$がスタートからの最短距離であることを示せば良いとわかります。
それを背理法で示します。
$k$回目に取り出される$v$についてその時点での$d(v)$が最短でないと仮定し、真の最短距離を$d^* (v)$とします。
そして$d^* (v)$を満たす経路において$v$の一つ手前に存在する頂点を$w$とします。
$w$について次の二通りで場合分けをすることができます。

#####  wがk-1ステップ目までに取り出される場合
$w$が$k-1$ステップ目までに取り出される場合
$w$を経由した経路が最短であることから$k$ステップ目が来るまで$d(v)$が更新されることはない
すなわち必ず$d(v) = d(w)+l(w,v)$のまま$k$ステップ目で取り出されることになる
よって$k$ステップ目で$v$が取り出されたとき$d(v)$が最短でないことに矛盾。


##### wがk-1ステップ目までに取り出されれない場合
$k-1$ステップ目までに取り出されるもののうち、$v_s\rightarrow \ v$の最短経路上にある最も$v$に近いものを$x$として,その後に$w$, $v$が続いているものとする。
この時$w$は$v$の最短経路上に存在することから
$d(w)\leq d(w) + l(w, v) = d(v)$を満たす。
このことから$k$ステップ目における最小の$d$は$d(v)$ではなく$d(w)$であることがわかり、
よって$k$ステップ目に$v$が取り出されるという帰納法の仮定に反する。

##### 結論
以上より背理法の仮定が正しくないとわかり、$k$ステップ目で$v$が取り出された時$d(v)$は$v_s\rightarrow \ v$までの最短距離であるとわかる。
このことから$k$ステップ目での定理の成立が示され、帰納法によって定理が示される。

## まとめ
出来る限りわかりやすくしようと思いましたが逆にわかりづらくなってしまったらすみません。
また、記事を書いた経験が少ないため、駄文になってしまっていたら申し訳ありません。
訂正等ありましたらご指摘いただけますと幸いです。



## 参考文献

この記事は以下の情報を参考にして執筆しました。

- データ構造とアルゴリズム 杉原厚吉　著