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

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

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

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

 



準備

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

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

 

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

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

特に、重み付き最短経路問題(weighted shortest path problem)は、各辺ごとに異なった重み(長さや移動時間)を与えて、「経路の重み合計を最小化する」意味での最短経路を探す問題です。

 

重み付き最短経路の求め方

より具体的に、次のグラフの重み付き最短経路を探してみましょう。まずは、辺の番号をそのまま図示します。

 

この時点では、グラフは頂点と辺の情報のみを持ち、重みの情報がありません。

 

グラフが持つ各辺に対して、ベクトルとして重みを定義し(重みベクトル weight vector)、それを図示してみましょう。

今回の重みの値としては、1から5の値をランダムに指定します。結果が再現されるように、「Random.seed!(2022)」で乱数のシードを指定しました。

「Edge 1 => 2」の重みは1、「Edge 1 => 3」の重みは5、といった対応関係です。

このベクトルを使ってグラフを描けば、各辺の重みがどうなっているかわかりやすいです。

 

重みを考慮した上で最短経路を探すには「a_star(グラフ, 始点,終点,距離行列)」という関数を用います。これはA*探索アルゴリズム(A* search algorithm)と呼ばれる方法で、最短経路を求めています。

ここで距離行列(distance matrix)\(D=(d_{ij})\)とは、

\[d_{ij}= \begin{cases}w_{ij}(始点i,終点jの辺の重み) & (始点i,終点jの辺がある )\\0 & (始点i,終点jの辺がない)\end{cases}\]

として定義される行列です。今回は向きのないグラフ(無向グラフ)を考えているので、「始点i,終点jの辺の重み」と「始点j,終点iの辺の重み」は等しく、対称行列として与える必要があります。

 

まず、さきほど定義した重みベクトルを、距離行列に変換しましょう。

「collect(edges(G1))[i].src」はi番目の辺の始点(source)、「collect(edges(G1))[i].dst」は終点(destination)です。行列\(D\)の辺に対応した成分に重みベクトルの値を代入しています。

始点と終点を入れ替えて同じ値を代入することで、向きのないグラフとして辺に重さを指定しました。

結果は確かに対応する部分が重みの値を持つ行列で、対称行列となっています。

 

こうして得た距離行列を使って最短経路を探してみます。

他の経路、例えば「Edge 1 => 3, Edge 3 => 4」の重みの合計はより大きいのく、確かに最短経路が求まっていますね。

 

最短経路の重みの合計を求める関数「path_weight_sum」を作ってみましょう。

最短経路を求め、その経路の辺ごとに重みの値を足していった結果を返します。

 

他の頂点でも、最短経路とその重み合計を求められます。

 

 

一般化

さて、今までやってきた計算を一般化してみましょう。

 

まず、重みベクトルを距離行列に変換する関数「distance_matrix」を作ります。

確かにさきほどと同じ結果が得られます。

 

さらに、最短経路と重みの合計を求め、最短経路を図示する関数「shortest_path_plot」を作りましょう。

最短経路の色づけについては、重みの等しい最短経路問題で作った関数と同じです。

 

ひと目で結果がわかるようになりました。

 

別のグラフ、別の重みで試してみましょう。

各辺の重み、最短経路、最短経路の重みがひと目でわかります。

 

別の頂点について試してみましょう。

 

 

 

 

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

各辺が異なる重みを持つケースでは、手計算で最短経路を求めるのがより難しくなるので、コンピュータで求められると嬉しいですね。

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

 

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

 

こちらもおすすめ

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

重み付きグラフ、最小全域木の問題とは? クラスカル法による解き方

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