文系 Hadooper でも分かる Dijkstra アルゴリズム
今日の Hadoop ソースコードリーディングで Dijkstra アルゴリズムの知名度が低かったので, 解説を書いてみたぜ.
用語が分かんないんだけど...
グラフというと y = 2x とかを思い浮かべるかもしれないが, この場合の「グラフ」というのは「いくつかの丸 (= ノード, 節) を線 (= エッジ, 辺) でつないだもの」で, 状態遷移図もグラフの一種. 状態遷移図は「有向グラフ」と呼ばる. 丸と丸とをただの線ではなく矢印でつなぐので「有向」=「向きが付いている」と言う.
"DAG" は "Directed Acyclic Graph" の略で「非循環有向グラフ」と訳される. "Directed" と "Acyclic" の順序が逆になってるのは気にせんでくれい.
このアルゴリズムの目的って?
概要で書いた通り, このアルゴリズムの目的はある地点への最短経路を求めること.
特徴としては, 探索が終わったときには全ノードへの最短経路が求まっている. つまり, あるゴールへの最短経路だけを求めたい場合には無駄な処理をしている可能性がある.
では, すっごく単純な例から.
上の図ではノードが 2 つで, 左のノードが始点 (スタートノード) だ.
Dijkstra 法ではまず始点から 1 ステップで到達できるノードを調べるぞ. 今回は調べる対象が右のノード 1 つしかないので, 1 回の探索で終了だ. もちろん, 右のノードへの最短経路は唯一あるエッジでその距離は 1 だ.
ちょっとだけ複雑に.
「って, どこが複雑やねん!? バカにしんといて!!」という声が聞こえますが, あーあー聞こえない(-"-;
今回はノードが 3 つで, スタートノードの他にノード「い」とノード「ろ」がある. Dijkstra 法では始点から 1 ステップで到達できるノードが複数あるときは, 始点に最も近いノードをまず選ぶ.
「選んでどうするんだ?」と思ったかな? 実はその選んだノードは最短経路が確定するんだ. 今回の例で言えば, 始点から「い」へは距離 3, 「ろ」へは距離 2 なので,「ろ」への最短経路「S → ろ」が確定してその距離は 2 だ.
次は, 最短経路が確定している「S」と「ろ」から 1 ステップで到達できるノードを調べる. (「S」への最短経路は「動かないこと」で距離は 0 ね.) この例では「S」から「い」へ到達できる経路しかないので, これが選ばれる.
選ぶ基準はちょっと複雑で「スタートノードからの最短距離が最短なもの」となる. これについては後の例で解説する.
「ろ」への最短経路「S → ろ」が確定し, 全てのノードへの最短経路が確定したので Dijkstra 法終了!
ほら, この例だけでもステップは複雑になったでしょ? この例の手順を理解すると後が楽だよ.
さらに複雑に. 経路が複数ある!
今回は前回の例に 1 本エッジを足してみた例だ.
これまで解説した部分は今後はさらっと流すことにする.
まず「ろ」の最短経路「S → ろ」が確定し, 最短距離が 2 と分かる. 次に「い」への最短経路を調べるのだが, 最短距離が確定しているノードから「い」へ到達する道が 2 つある. 「S → い」と「ろ → い」だ.
「そんなん『S → い』を選ぶに決まっとるやん!」というツッコミはスルーして, 丁寧に選択しよう.
ここで 2 つの経路を選ぶ基準は「スタートノードからの最短距離が最短なもの」だった. この例では「S → い」が距離 3, 「S → ろ → い」が 4. 「S → い」の方が短いので, こっちが最短経路として確定する. これで Dijkstra 法は終了.
この丁寧な選択は問題が複雑になってきたときに非常に効くし, ここが Dijkstra 法のキモだと言っていい.
さらっと次の例に. 本格的な例.
ノードが 1 つ増え, エッジが 3 つ増えたな. この例が分かれば, 一般のグラフの場合を理解できるはず.
では手順の解説. まず「S」から最も近い「ろ」への経路が決定する.
次が複雑だ! 重要だ!
最短経路が求まっているノードは「S」と「ろ」. するとそれらから 1 ステップで行けるノードは「い」と「は」. まずはスタートノードからそれぞれへの最短距離を求める.「い」は「S → い」の距離 3. 「は」は「S → は」が距離 4,「S → ろ → は」が距離 3 なので, 「S → い」と「S → ろ → は」の経路がそれぞれ「い」と「は」への最短経路だと確定する.
『「は」へ到達するルートは「S → い → は」も残ってるじゃないか!?』というツッコミに対してちょっと解説すると, Dijkstra 法の探索は始点からの距離が短い順に行っている. だから常に「最短距離が確定したノードへの距離」は「最短経路が確定していないノードへの距離」より短いのだ. これを保っているルールがさっきの「スタートノードからの最短距離が最短なもの」を選んでいくというやつだ.
それで計算する間でもなく「S → ろ → は」が「は」への最短経路だと分かる.
そろそろ Dijkstra 法の感覚が掴めてきたかな??
これでアルゴリズム初心者向けの解説は終了. アルゴリズムの実装は http://www.deqnotes.net/acmicpc/dijkstra/ とかを見てくれれば良いはず.
最後に
自分は数学を専攻していたのだが, こういう専門知識を分かりやすく解説するという仕事も自分の責務だと思っている. それが大学, 大学院という穀潰し生活をさせてくれたことへの恩返しだなぁと最近は感じている.
なので, 「ここが変だ」「ここが分からん」「この話題も解説せい」等のツッコミ・要望は大歓迎. コメントに書くのが気が引ける場合は Twitter でどうぞ.
つ【http://twitter.com/cocoatomo】
