最短経路 ― shortestPath / allShortestPaths

導入

第1章で紹介した「経路探索」を、実際にCypherで書いてみましょう。Neo4jには、最短経路を求める組み込みの機能が用意されています。

説明

MATCH p = shortestPath((a:Person {name: 'Alice'})-[:KNOWS*]-(b:Person {name: 'Carol'}))
RETURN p

• shortestPath(...) … 丸括弧の中に書いたパターンに沿って、a から b までの最短経路を1つ求める関数。
• p = shortestPath(...) … 求まった経路全体に p という変数名をつける。経路にはたどったノードとリレーションシップがすべて含まれる。
• [:KNOWS*] … 第4章で学んだ可変長パス。「KNOWS を何回でもたどってよい」という条件を、最短経路探索の対象範囲として使う。

graph LR
    Alice((Alice)) -- KNOWS --> Bob((Bob))
    Bob -- KNOWS --> Carol((Carol))
    Alice -. "shortestPath" .-> Carol

shortestPath は「最短の経路を1つだけ」返します。もし同じ長さの最短経路が複数存在する場合に、そのすべてを知りたいときは allShortestPaths を使います。

MATCH p = allShortestPaths((a:Person {name: 'Alice'})-[:KNOWS*]-(b:Person {name: 'Carol'}))
RETURN p

最短経路探索は、SNSでの「2人の関係の近さ」を調べたり、路線図で「乗り換え回数が最も少ないルート」を求めたりする場面でそのまま応用できます。第3章・第4章で学んだ「パターンをたどる」という発想の延長線上に、この最短経路探索があることを意識しておきましょう。