グラフアルゴリズムを1から — 最短経路とその応用

乗換案内からベクトル検索まで、世界の裏側は「点と線」で動いている。BFS・ダイクストラ法・A*を前提知識ゼロから積み上げ、最後はLLM時代の検索を支えるHNSWまで一本の道でつなぐ。

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

世界は「点と線」でできている

駅の路線図を思い浮かべてください。駅が点で、駅と駅を結ぶ線路が線。地図の縮尺も駅間の実距離も無視して、「どこと どこが つながっているか」だけを描いた図です。この「点と線のつながり方だけを抜き出した構造」を、数学ではグラフと呼びます。点は頂点（ノード）、線は辺（エッジ）です。

グラフの守備範囲は路線図にとどまりません。SNSのフォロー関係（人が頂点、フォローが辺）、Webページとリンク、道路網、分子の原子と結合、そしてニューラルネットの層のつながりまで、「何かと何かの関係」はほぼすべてグラフで書けます。関係に向きがあるもの（フォローは一方通行）は有向グラフ、なければ無向グラフ。辺に「所要時間」や「距離」のような数値が付いていれば重み付きグラフと呼びます。

グラフに対する問いで最も基本かつ最頻出なのが、この記事の主題である最短経路です。「AからBまで、いちばん安く行くにはどう進むか」。カーナビも乗換案内もゲームの敵キャラの追跡も、そして後半で見るベクトル検索も、突き詰めればこの問いを解いています。

同じ「最短」でも2種類ある

最短経路には実は2つの顔があります。

• 通る辺の本数を最小にしたい: 「乗換回数が最少の経路」。すべての辺のコストが同じ（=1）とみなせる場合
• 辺の重みの合計を最小にしたい: 「所要時間が最短の経路」。辺ごとにコストが違う場合

前者を解くのがBFS、後者を解くのがダイクストラ法です。この区別を最初に押さえておくと、この先の道具の使い分けで迷いません。

BFS: 波紋のように広がる探索

幅優先探索（Breadth-First Search、BFS）は、池に石を落としたときの波紋のイメージです。出発点から「1歩で行ける頂点」を全部見て、次に「2歩で行ける頂点」を全部見て——と、近い順に輪を広げていきます。

実装の道具はキュー（先入れ先出しの待ち行列）ひとつ。出発点をキューに入れ、取り出しては「その隣でまだ見ていない頂点」を印を付けてキューの末尾に足す。これを繰り返すだけです。波紋は近い順に広がるので、ある頂点に最初に到達した瞬間の歩数が、そのままその頂点への最短ホップ数になります。後からもっと短い道が見つかることはありません。

コストは、頂点数を $V$、辺数を $E$ とすると $O(V + E)$。各頂点と各辺を高々1回ずつ触るだけの、いわば線形時間です。一方、「経路を全部列挙して最短を選ぶ」素朴な方法は、経路の数が組合せ的に爆発するため指数時間になります。この差がどれほど桁違いかは、下の図で $n$ を動かすと体感できます。

ダイクストラ法: 「確定」を安い順に積み上げる

辺に重みが付くと、BFSは壊れます。「2本の辺で合計10分」の道より「3本の辺で合計6分」の道が速いことがあるのに、BFSは辺の本数しか見ないからです。重み付きの世界では「近い順に輪を広げる」の「近い」を、歩数ではなく累計コストで測り直す必要があります。

そこでダイクストラ法（Dijkstra's algorithm、1956年にエドガー・ダイクストラが考案）。イメージは、出発点から水を流し、低い土地から順に水没していく様子です。アルゴリズムは「暫定の距離が最小の頂点」を1つずつ取り出し、その頂点への最短距離を確定させます。取り出す道具はキューではなく優先度付きキュー（常に最小値から取り出せる待ち行列）。頂点 $u$ を確定させたら、$u$ の隣の各頂点 $v$ に対して次の更新を試みます。