Neo4jで最短経路計算をする手段の使い分け

##記事を書いた理由
Oracle PGXやNeo4jなどといったGraph DBの最短経路クエリについて調べているうちに、最短経路を取得する方法には以下の２つがあることを発見しました。

1. クエリ内で最短経路を取得する
2. 最短経路計算をするアルゴリズムを呼び出す

Neo4jで最短経路計算をするとき、この２つの方法をどのように使い分けるべきかをまとめてみました。

##前提：テストデータの取得

以下のクエリを実行し、テストデータの作成および確認をします。
（[こちら](https://qiita.com/kk31108424/items/715f82fa62db6040c805)の記事も参考にしてください。）

```sql

LOAD CSV WITH HEADERS FROM "https://gist.githubusercontent.com/lassewesth/634281cced11147432cf232a2c36e080/raw/1ed1f4fe4ca4c8092bbc8557addd1e5d87316833/eroads.csv" AS row
RETURN row
LIMIT 10
```

```sql
CREATE CONSTRAINT ON (p:Place)
ASSERT p.name IS UNIQUE
```

```sql
USING PERIODIC COMMIT 1000
LOAD CSV WITH HEADERS FROM "https://gist.githubusercontent.com/lassewesth/634281cced11147432cf232a2c36e080/raw/1ed1f4fe4ca4c8092bbc8557addd1e5d87316833/eroads.csv"
AS row

MERGE (origin:Place {name: row.origin_reference_place})
SET origin.countryCode = row.origin_country_code

MERGE (destination:Place {name: row.destination_reference_place})
SET destination.countryCode = row.destination_country_code

MERGE (origin)-[eroad:EROAD {road_number: row.road_number}]->(destination)
SET eroad.distance = toInteger(row.distance), eroad.watercrossing = row.watercrossing
```

##ホップ数のみを考慮する場合：クエリ内で最短経路を取得する
エッジの重みを考慮せず、単純にノードとノードのホップ数のみを考慮する場合は、クエリ内で最短経路を取得します。

```sql
MATCH p=shortestPath((start:Place {name: "Århus"})-[rels:EROAD*]-(end:Place {name: "Roma"}))
RETURN [place in nodes(p) | place.name][1..-1] AS journey,
       length(nodes(p)[1..-1]) AS intermediatePlaces,
       reduce(s = 0, r in rels | s + r.distance) AS total_distance
```

結果は以下のようになります。
<img width="1440" alt="スクリーンショット 2019-06-14 23.49.00.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/777a1ae6-c189-c896-825e-26c7f4e488d3.png">

##エッジの重みを考慮する場合：アルゴリズムを呼び出す
エッジの重みを考慮し、重みの総和が最小になる経路を求めたい場合は、適切なアルゴリズムを呼び出します。

```sql
MATCH (start:Place{name:"Århus"}), (finish:Place{name:"Roma"})
CALL algo.shortestPath.stream(start, finish, "distance")
YIELD nodeId, cost
MATCH (n) WHERE id(n)=nodeId
return n.name, cost
```
結果は以下のようになります。

<img width="1440" alt="スクリーンショット 2019-06-14 23.59.18.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/f1e0ef01-88f8-3c2a-d465-bf06ad30691a.png">

先ほどのエッジの重みを考慮しない、最小ホップ数を持つ経路のコストと比べると、コストの総和が小さくなっているのがわかります。

この裏側では、ダイクストラ法というアルゴリズムが動いています。

###補足：ダイクストラ法とは
ダイクストラ法とは、エッジの重みが全て０以上の場合、ある一つの始点からの最短経路を求めるのに最適なアルゴリズムのことです。

>ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
[Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95)より引用

##ダイクストラ法以外で最短経路を求めたい場合：適切なアルゴリズムを呼び出す
上記のように、ダイクストラ法では、（全てのエッジの重みが０以上の場合グラフにおける）最短経路を求めることができました。

しかし、求めたい経路が最短経路以外の経路である場合、ダイクストラ法以外のアルゴリズムを使う必要があります。

###例：ÅrhusからRomaまでの３番目に短い経路を求めたい場合

私たちがカーナビを使用する時、いくつかのルートが表示されますよね。例えば、「最短経路上の道路では渋滞が発生しているので、２番目に短い迂回ルートで目的地まで向かう」といった場合、最短経路以外の経路（２番目に短い経路）も求めておく必要があります。（カーナビでの経路探索は、[こちら](https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/research/publications/2015/sigspatial_kshortest.pdf)の論文に詳しく書かれています。）

この時に使用するアルゴリズムは、`Yen's algorithm`です。`Yen's algorithm`とは、K番目(ある文脈では1~K番目)に短いパスを見つけてくれるアルゴリズムです。詳しい計算の流れは[こちら](https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22)の記事に書いてあります。

実際にNeo4jで試してみます。

```sql
MATCH (start:Place{name:'Århus'}), (end:Place{name:'Roma'})
CALL algo.kShortestPaths.stream(start, end, 3, 'cost', {})
YIELD index, nodeIds, costs
RETURN [node in algo.getNodesById(nodeIds) | node.name] AS places,
       costs,
       reduce(acc = 0.0, cost in costs | acc + cost) AS totalCost
```
結果は以下のようになります。

<img width="1440" alt="スクリーンショット 2019-06-16 14.47.31.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/7d9be639-d719-ce85-6379-bb691660b11b.png">

このように、アルゴリズム呼び出し時に指定した数字k（ここでは3）番目に短い経路を求めることができます。

`Yen's algorithm`を呼び出す時、デフォルトではパスを返すことはありませんが、引数に`path: true`を渡してあげると、パスで結果を返してくれます。

```sql
MATCH (start:Place{name:'Århus'}), (end:Place{name:'Roma'})
CALL algo.kShortestPaths.stream(start, end, 3, 'cost', {path: true})
YIELD path
RETURN path
LIMIT 3
```
<img width="1440" alt="スクリーンショット 2019-06-16 15.00.44.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/c0c018d5-9d6c-5123-e99a-6883d450d689.png">

（パスで結果を返してくれるのですが、経路の長さを直感的に判断できないので、若干わかりづらいですね笑）

##蛇足：Yen's Algorithmで最短経路を求めてみた
上記のように、`Yen's Algorithm`はK番目(ある文脈では1~K番目)に短いパスを見つけてくれるアルゴリズムでした。

それでは、K=１の場合、最短経路を求めることができるのではないかと考え、実行してみました。

```sql
MATCH (start:Place{name:'Århus'}), (end:Place{name:'Roma'})
CALL algo.kShortestPaths.stream(start, end, 1, 'cost', {})
YIELD index, nodeIds, costs
RETURN [node in algo.getNodesById(nodeIds) | node.name] AS places,
       costs,
       reduce(acc = 0.0, cost in costs | acc + cost) AS totalCost
```

<img width="1440" alt="スクリーンショット 2019-06-16 15.59.31.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/e8f2ad3c-b491-8d8d-dbdc-bb1985e808b0.png">

このように、`Yen's Algorithm`でも最短経路を求めることができました。

しかし、なぜ最短経路を求める際は、`Yen's Algorithm`を使用しないのでしょうか？

その理由は、**計算量**にありました。

`Yen's Algorithm`の大まかな流れを以下に示します。

1. まず最短経路をダイクストラ法で求める。
2. 最短経路から分岐した経路(deviation path)を計算する。

>Our implementation uses Dijkstra algorithm to find the shortest path and then proceeds to find k-1 deviations of the shortest paths.
[Neo4jの公式サイト](https://neo4j.com/docs/graph-algorithms/3.5/algorithms/yen-s-k-shortest-path/)より引用

まず、ダイクストラ法の計算量はO(V²)です。
`Yen's Algorithm`の場合は、（エッジの重みが全て非負の場合）ダイクストラ法に加えて第二最短経路、第三最短経路…と計算していくので、直感的に計算量が大きくなることがわかります（正確にはO(KV³)）。

最短経路のみを求める場合であれば、計算量の少ないダイクストラ法を用いる方が効率的ですね。

この他にも、Neo4jには様々なアルゴリズムが実装されています。詳しく知りたい方は、[こちら](https://neo4j.com/docs/graph-algorithms/3.5/algorithms/pathfinding/)をご覧ください。