優先探索は、頂点と辺のつながりの情報だけが与えられていたが、辺に移動コストの数値が定義されているときに、スタートするノードからゴールするノードまでの総コストが最小になるような経路と総コストを求める探索を最短経路探索と呼ぶ。最短経路探索には、有名なダイクストラのアルゴリズムがあり、ここではそれをNeo4jで実装してみる。コストはNeo4jのプロパティで表現することができる。プロパティグラフを容易に扱えるNeo4jにとって非常に役に立ち、わかりやすい例題である。ダイクストラ法ダイクストラ法の簡単な解説とアルゴリズムは、こちらにあります(Qiitaは実装例は多いけど解説は意外と少ない)。スタートノードに隣接するノードを探し、その中で最もコストが小さいものは、そのノードへのコストの最小値として確定することができる。それを繰り返していき、コストの最小値を次々と確定させて、最終的にゴールのノードのコストが確定したら終了したらよい。下図にダイクストラ法の実行のイメージを示す。ここでは品川から久里浜に至る経路を探索している。左のコストテーブルが、コストが確定していく順番のイメージである。自前でダイクストラ実装例を下に示す。このプロシージャは、スタートとゴールのノードidをもらって、その最短経路のパスと総コストを求める。返却値は必ず一つで、複数同じコストのパスがあるケースには対応していない(最初に見つかったパスが返却される)。ダイクストラ法をナイーブに実装するとO(N^2)の計算量になるが、ノードをコストの小さい順に並べるプライオリティキューを利用することによって、計算量を減らすことができる。下のプログラムでは、ノードとコストの対応とノードのコストが確定済みかをクラスNodeInfoを利用して管理している。よって、プライオリティキューにはNodeInfoのオブジェクトを入れている。その順序はNodeInfoのcostの比較によって並べ替えられている(比較関数がラムダ式で定義されている)。NodeInfoの情報は、ノードと対応をつけてmapで管理している。パスを得るためのノードとその一つ手前の関連の対応を管理するマップも幅優先探索などと同様に使っている。コストを表すプロパティは、変数cost_propertyに定義している。ここでは"cost"という名前を使っている。データベース上にこのプロパティがあることが前提とされる。この文字列をプロシージャのパラメータに入れるほうが、柔軟になるが、その改造は容易である。}幅優先探索のときと同じサンプルでこのプログラムを実行してみよう。以下のサンプルである。ちなみに関連のコストは以下のようになっている。A(idは0)からF(idは5)へ至る最短経路を求める実行結果は、以下の通りである。(幅優先などと同じようにすべてのノードへの最短経路を求める例題も追加するかもしれない。最短経路木が同様に書ける)組み込み関数でダイクストラNeo4jには組み込みでダイクストラ法は実装されている。それを利用する方法は、こちらにある。upLoginユーザーは見つかりませんでした。