グラフ理論
最近、プログラムを組む時にグラフ理論を使用する機会が何度かありました。
これからも使えそうですし、覚えていて損はなさそうなので
この機会に簡単にまとめてみました。
グラフってあのグラフ？
グラフと聞いて何を思い浮かべるでしょうか。
よく使うのはExcelなどで書く棒グラフや折れ線グラフでしょうか。
グラフ理論で扱うグラフは普段使うグラフとは少し違います。
丸と丸を線でつないだこのようなものを グラフ と呼びます。
この丸のことを 頂点（ノード） 、線のことを 枝（エッジ） と呼び
ノードとエッジの集合であるグラフに関する数学の理論を グラフ理論 といいます。
ケーニヒスベルグの橋
グラフ理論は一般に「ケーニヒスベルグの橋」と呼ばれている問題が
起源と言われています。
ケーニヒスベルグの橋 とは
「この川にかかっている7つの橋を同じ橋は2度通らずに、
全て渡って元の所に帰ってくることができるか」という問題です。
オイラーという数学者はこの問題を上記のグラフに置き換えて考えました。
このグラフが一筆書きできれば、橋を全て1度ずつ通って戻ってくることができます。
ちなみに、この問題の答えは「できない」です。
ある頂点につながっている枝の数を 次数 と呼び、
一筆書きができるのは次数が奇数の頂点の数が０または２のときのみだからです。
このように現実の問題をグラフに置き換えることで、
グラフ理論の定理・理論などを使って問題を解決することができます。
現実では
- 目的の駅に一番早く着く経路は？
（最短経路問題）
- 複数の場所を1回ずつ巡回する場合の最短の経路は？
（巡回セールスマン問題）
などの問題をグラフ理論で解くことができます。
参考：「グラフ理論」と「組み合わせ最適化アルゴリズム」の教科書PDF
今回は実際の私が使う必要のあった最短経路問題について説明します。
最短経路問題
グラフの与えられた2つのノード間を結ぶ経路の中で最短の経路を求める問題、
今回はおそらくもっとも有名で実装が比較的簡単そうな
ダイクストラ法で解いていきます。
ダイクストラ法のアルゴリズム
- 開始ノードに確定フラグを立てる。
- 確定フラグを立てたノードから辿れる未確定ノードの最短経路の距離を計算する。
- 確定フラグを立てたノードから辿れるノードの内、開始ノードからの最短経路の距離が最小のノードに確定フラグを立てる。
- すべてのノードに確定フラグが立つか、終了ノードに確定フラグが立つまで2,3を繰り返す。
距離が最小のノードから確定するので、距離が負のノードがあるときは使えません。
実際にダイクストラ法を使う場合は、
Pythonでは networkx というライブラリで簡単に実装できます。
以下が、自分で書いたものです。
未確定のノードの中で距離が最短のノードを決める際に、
heapq モジュールを使用して優先度付きキューを実装しています。
あとは、アルゴリズム通りの作りになっているはずです。
簡単な使用法と使用結果について少し。
今回はこのグラフを仮定してテストしました。
【入力】
開始ノード - a
終了ノード - h
【期待する出力】
a → d → g → h
期待する出力になっていますね。
2つのテストパターンしか行っていないので不安ですが、今回はこれまで。