Julia(Graphs)で最短経路問題を解き、図示する方法

どうも、木村(@kimu3_slime)です。

今回は、Julia(Graphs)で最短経路問題を解き、図示する方法を紹介します。

前提知識:Julia(Graphs)でグラフ理論におけるグラフ作成、次数、隣接行列を求める方法

 

準備

Graphs, GraphPlot,Colorsを使うので、持っていなければインストールしておきましょう。

準備として、以下のコードを実行しておきます。

 

最短経路問題を解き、図示する方法

最短経路問題(shortest path problem)は、与えられたグラフの2つの頂点間の距離を最も短くするような経路を探す問題です。

一般的には、各辺ごとに異なった重み(長さ、移動時間)を考えることができます。ただし今回は、どの辺も等しい重み(1)を持つケースを考えます。

 

より具体的に、次のグラフの最短経路を探してみましょう。

 

「a_star(グラフ, 始点,終点)」で、グラフの始点から終点までの経路を求めてくれます。

これはA*探索アルゴリズム(A* search algorithm)と呼ばれる方法で、ダイクストラ法(Dijkstra’s algorithm)を一般化したものとなっています。評価関数をうまく選んで、その情報を使いながら始点から経路の木をひとつずつ伸ばしていく探索法です。

経路は辺を成分とするベクトルとして返ってきます。頂点1と4を結ぶ最短経路は、1から2、2から4へと進むもの、ということです。

length関数を使えば、そのベクトルの成分数、つまり最短経路の長さが求められます。

 

 

この結果をわかりやすくするために、図示してみましょう。

グラフをプロットする関数gplotは、edgestrokecというオプションで辺に色を指定できます。

色の指定は配列で行うことができ、例えば4番の辺にオレンジ色をつけたいなら、「colors[4]=colorant”orange”」とします。

上のコードでは、まずすべての辺に対して通常色を与える配列colorを作ります。そして、最短経路に含まれるすべての辺に対し、indexinでその辺が何番目なのかを取り出し、その番号のcolorをオレンジ色にしました。

これで最短経路がひと目でわかるようになりましたね。

 

以上の結果を一般化して、最短経路とその長さを求め、それをプロットする関数を作りましょう。

色をつける部分でif文による分岐が加わっています。それは次の理由です。

グラフの辺としては「Edge 1 => 2」があるのですが、indexinで番号を取り出すときに、(無向グラフであるにもかかわらず)「Edge 2 => 1」は存在しないとなってしまうためです。

(「has_edge(G1,2,1)」という関数を使えば、この辺はグラフに確かに存在することがわかりますが、この関数では辺の番号が取り出せません。)

そこで、if文で分岐を加え、逆向きの辺を得る「reverse(辺)」を合わせて色の追加をすることにしました。もう少し簡単な記述方法があるかもしれません。

 

これを使えば、頂点を与える順序に関わらず、最短経路が求められます。

 

 

 

ケーニヒスベルクの橋のグラフで、最短経路を求めてみます。

 

 

 

もう少しサイズの大きなグラフとして、正20面体グラフにおける最短経路を求めてみましょう。

 

 

 

以上、Julia(Graphs)で最短経路問題を解き、図示する方法を紹介してきました。

頂点数や辺の数が増えるほど、最短経路を手計算で求めるのは難しくなりますが、コンピュータだと簡単に早く解けるので嬉しいですね。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

Julia(Graphs)でグラフ理論におけるグラフ作成、次数、隣接行列を求める方法

グラフ理論入門:グラフとは、グラフの同型

グラフ理論における経路、連結性とは?

グラフ理論における次数、握手の補題とは

一筆書きができる条件、オイラーグラフとは