akimachoのはてなブログ

ICTとデザインのためのブログ

『プログラミングの基礎』読書日誌-15日目-

はじめに

f:id:akimacho:20150310144408j:plain

今日は,ダイクストラアルゴリズムダイクストラ法)について勉強していきます.ちなみに写真の人物はエドガー・ダイクストラ(E.W.Dijkstra)です.

エドガー・ダイクストラ - Wikipedia

追記

計算量について書きました.

ダイクストラアルゴリズム

ダイクストラアルゴリズムは,重みつきグラフ(ネットワーク)上の2点を結ぶ最短路を求めるアルゴリズムです.ダイクストラ法とも呼ばれています.このアルゴリズムの内容に入る前に,ダイクストラアルゴリズムに必要な用語を箇条書きします.

  • グラフG・・・点とこれらを結ぶいくつかの変から構成されるもの
  • V(G)・・・グラフGの点の集合
  • E(G)・・・グラフGの辺の集合
  • 重み・・・点や辺に付けられた値.長さともいう
  • 重みつきグラフ・・・グラフの各辺に対して重みが付けられているグラフ.ネットワークともいう
  • 重み関数・・・グラフGの各辺から実数への写像
  • 最短(経)路・・・グラフGの2点を結ぶ経路の中で長さが最小となる経路
  • 最短距離・・・最短路の長さ

それではアルゴリズムの内容についてみていきましょう.今回は上野修一・高橋篤司『情報とアルゴリズム』(森北出版)p.93に書かれている記述も参考にしてみました.項目を入力・出力・ステップ1〜ステップ7に分けて説明します.

情報とアルゴリズム (電子情報通信工学シリーズ)

情報とアルゴリズム (電子情報通信工学シリーズ)

入力

連結グラフG,重みつき関数w:E(G) \to \it R^+,2点a, b \in V(G)

グラフGと重み関数wにより重みつきグラフ(ネットワーク)が定義されます.点aは始点,点bは終点を表しています.

出力

重みつきグラフ(G,w)の最短路と最短距離

ステップ1

始点への距離\lambda(a) = 0と確定しておき,それ以外の点vへの最短距離 \lambda(v) = \inftyと仮定しておく.

ステップ2

\it Xを最短距離が確定した点の集合,\it Yを最短距離がまだ確定していない点の集合とする.最初は集合\it Xには始点以外のすべての点が,集合\it Yには始点aのみが入る.図にすると次のようになる.

f:id:akimacho:20150311102757p:plain

ステップ3

集合 \it Y空集合 \emptysetになったら,すべての点への最短距離が確定したことを意味するので終了する.つまり以下の図のようになる.

f:id:akimacho:20150311102810p:plain

ステップ4

直前に確定した点につながっている点について,その最短距離を更新する.

「その点がすでにもっている最短距離 \lambda(v) 」と「直前に確定した点経由でその点に行った場合の最短距離\lambda(s) + w(s,v)」を比べ,短い方をその点への最短距離とする.

ステップ5

集合/it Yの中で,最短距離が最小の点pを選択する.

ステップ6

 pの保持している最短距離を確定し,点 pを集合 \it Yから集合 \it Xに移す.

つまり, \it X = \it X \cup \left\{ p \right\} \it Y = \it Y \setminus \left\{ p \right\}

ステップ7

ステップ3へ.

計算量

『プログラミングの基礎』では書いてありませんが,ダイクストラアルゴリズムの最大時間計算量は O(n^2)です.『情報とアルゴリズム』(森北出版)p.p93-96に証明が書いてありました.

今までのメトロネットワーク最短路問題への取り組み

ローマ字の駅名が入力されたら,その距離がわかるようになってます.つまりグラフの点とその辺の重みをプログラムにより求めることができるようになっているわけです.


メトロネットワーク最短路問題その1

練習問題

ステップ1をコードにします.問題12.2~12.3はテストが辛そうなので目で確認,問題12.4は答えにあったテストケースを使いました.


メトロネットワーク最短路問題その2

おわりに

ダイクストラアルゴリズムについては,ルーティングプロトコルのひとつ,OSPF(Open Shortest Path First)に用いられているという以上のことは知りませんでした.なので,今回,アルゴリズムの詳細を知ることができてよかったです.

Open Shortest Path First - Wikipedia

30 Minutes Networking No.RT5

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)

情報とアルゴリズム (電子情報通信工学シリーズ)

情報とアルゴリズム (電子情報通信工学シリーズ)