データ構造におけるYenのk最短経路アルゴリズム徹底解説

単一の最短経路だけを返すのではなく、イエン(Yen)のk最短経路アルゴリズムでは、k本の最短経路を求めることができます。これにより、2番目に短い経路、3番目に短い経路といった具合に、順位の異なる複数の経路を順番に取得できるのが大きな特徴です。

例として、地点Aから地点Bへ移動しなければならない場面を考えてみましょう。地点Aと地点Bの間には複数のルートが存在しますが、その中から時間計算量の観点で無駄のない真の最短経路を見つけ出し、目的地まで効率よく到達する必要があります。

具体例で理解する

下図の例を、頂点Bが「ピーク(頂上)」になっている橋だと考えてください。ある人が地点Aから地点Cへ橋を渡りたい場合、わざわざ頂上のピークを経由して渡る人はいません。つまり、AからCへの実際の通行経路は、見かけ上より少し長い経路になるということです。

最短経路を求める手法は複数存在しますが、ここでは(k-1)番目までの最短経路を順に求めていくことを考えます。

アルゴリズムの仕組み

イエンのアルゴリズムは、まずダイクストラ法などを用いて通常の最短経路を1本求めます。次に、すでに得られた経路上の各ノードを一時的に除外したグラフ上で最短経路を再計算し、元の経路から分岐する候補経路(スポア経路)を生成します。これらの候補の中から最もコストの小さいものを取り出す操作を繰り返すことで、2番目、3番目……とk本の最短経路を順に列挙していきます。

k最短経路アルゴリズムの実装例

以下は、グラフデータベースNeo4jで提供されるalgo.kshortestPathsプロシージャを利用した実装例です。開始ノードと終了ノードを指定し、「distance」をコストとして上位10件の経路をストリーム形式で取得し、Pandasのデータフレームとして表示しています。

query = """
MATCH (start: Place {id: $source}), (end: Place {id: $destination})
CALL algo.kshortestPaths.stream(start, end, 10, 'distance')
YIELD nodeIds, costs, index
RETURN index,
    [nodeId IN nodeIds[1..-1] | algo.getNodeById(nodeId).id] AS via,
    reduce(acc = 0.0, cost IN costs | acc + cost) AS totalCost
"""

params = {"source": "Alex", "destination": "US"}

with driver.session() as session:
    rows = session.run(query, params)
    df = pd.DataFrame([dict(record) for record in rows])

pd.set_option('max_colwidth', 100)
display(df)