某芸人兼YouTuberの動画内で取り上げられていた企画「Wikipediaゴルフ」。この最短経路を自動で求めてくれるウェブサイトを作りました。
フロントエンドにNext.js、バックエンドにFastAPIを用いて、Vercel上にデプロイしています。
- 🔗 サイトはこちら
- 🔗 GitHubリポジトリ
wikipediaゴルフとは
ある記事から、リンクを辿り目的の記事まで最短何打で行けるかを競うゲーム。
仕様方法
- 上に乗せたリンクから、本サイトに飛ぶ
- 「START」と書かれたフォームに、スタート記事を入力
- 入力候補が出てくるのでヒットしているものをクリック
- GOALも然り
- 「経路を探索する ⛳」ボタンをクリック
実行結果
アルゴリズムを解説
この最短経路には幅優先探索を用いています。これ自体の解説は、私以上にわかりやすい記事がたくさんあったのでリンクを貼っておきます。
データベーススキーマ
nodes
| カラム名 | 説明 |
|---|---|
| node_id | 主キー |
| name | 記事名 |
| is_redirect | 記事本体ではなく、表記揺れ（リダイレクト）かどうか |
| is_orphan | どこからもリンクされていない孤立記事かどうか |
edges
| カラム名 | 説明 |
|---|---|
| from_node | node_idの外部キー |
| to_node | node_idの外部キー（from_nodeの記事内にあるリンク先） |
リダイレクトについて
Wikipediaには「バキ童」と「春とヒコーキ」のように、表記揺れをある程度吸収するための別称（リダイレクト）が数多く登録されています。is_redirectは、その別称記事かどうかを区別するためのフラグです。
BFS高速化への道
一度プレーンのBFSアルゴリズムを組んでみたんですが、どえりゃ重い。
なので、高速化するためにいろいろな手を打ちました。
1. 双方向BFSという革命
一番効果が大きかったのがこの改善です。スタート地点とゴール地点両方から挟み込むように探索を行います。片方向とは比べ物にならないくらい高速になります。
E=１記事当たりの平均記事数 D=最短経路の打数 N=比較数
片方向の場合
N = E ^ D
双方向の場合
N = 2E ^ \frac{D}{2}
指数部分の変化を見れば、その差は一目瞭然！！
2. DBのインデックスすごい
もう一つ効果が大きかったのが、DBにINDEXを貼ることです。
正直詳しいことはわかっていないですが、いわゆるDBに索引をつけれるようになるらしいです。
DBのインデックスを理解しよう
3. prismaが遅すぎる
開発初期は、バックエンドもtypescriptで賄おうとしていました。DBへの接続はORMのprismaを用いて。しかし、どうやらprismaは一クエリごとにDBの接続と切断をしているのか詳しい原因はわかりませんが、めちゃくちゃ時間がかかりました。なので、バックエンドはいっそのことFastAPIに乗り換えることにしました。（ぶっちゃけ今までpythonばかりやってたからやりやすいっていうのもある。）
4. クエリ投げすぎ
従来のBFSのアルゴリズムはキューを用いて、次の探索ノードを格納することでBFS特有の動きを実現していました。しかしそれでは、ノード一個見るごとに子要素を得る必要がありクエリを投げることになる。でら遅い。
なので、今回はBFSの一層すべてを一括で取得するようにしている。例として片方向の場合を記す。
def finder(s,g): # s = スタート記事 g = ゴール記事
# queueを廃止
# 一層のノードすべてを記憶する
frontier = {s}
parent = {}
while True:
# frontier(一層すべて)の子要素を取得する。この時に親も子も両方取得する
query = "SELECT from_node, to_node FROM edges WHERE from_node = ANY(%s)"
cur.execute(query, (list(frontier),))
# 下階層のすべてのノードを保存する
next_frontier = set()
for from_node, to_node in cur.fetchall():
if to_node not in parent and to_node != s:
parent[to_node] = from_node
# 子ノードを保存
next_frontier.add(to_node)
# ゴールかどうかの判定
if to_node == g:
# parentをたどってパスを生成し終了
return parent_connector(to_node, parent)
# 新しい子の層を代入
frontier = next_frontier
SQLの結果はDBの昇順で返ってくるため、frontier内の順番とは一致しません。子ノードだけを取得すると「誰の子か」が分からなくなってしまうため、親ノードと子ノードを同時に取得するようにしています。
注意点・改善点
実装版は記事数を削減している
なんせ金がない大学生なので、今回のデプロイはすべて無料枠で行っています。それ故にDBがわずか0.5GBしか使えない！！
なので実装版では、引用される回数が少ないものから間引いていっています。
（2026年7月時点）
| 記事数 | ファイルサイズ合計 | |
|---|---|---|
| 全記事 | 2,459,112件 | 5,829MB |
| 実装版 | 42,914件 | 238MB（削りすぎました） |
最短経路が7打以上の場合は強制終了される
探索範囲が広くなりすぎてしまうため、最短経路が7打を超過してしまう場合は、BFSをやめるようにしています。しかし、後述しますが最短経路が7打以上になることはあまりないです。
リンクの取得が完璧じゃない
今回DB作成には「Wikipedia fundation」が公開しているXMLを加工して拾っています。しかし、そのXMLのフォーマットがちょいわけわかめで実は全リンク関係をとれているわけではないです。
おまけコラム
ページ右上の「おまけコラム →」をクリックすると、今回開発していて得れたデータがいろいろまとまっています。
5万回最短経路を求めて分かったこと
今回おまけとしてランダムな最短経路を５万回試行しました。その調査結果もまとめて書いています。
(5万回試行中の画面。表示されているリスト一つ一つが最短経路)
6次の隔たりを応用して最短経路の平均打数を予測しよう
6次の隔たりとは：
世界中のどんな二人の人間も、知人を介した平均約6人程度の仲介者をたどれば、間接的につながっているという仮説。人には知り合いが平均45人いるとされていて、6人仲介すると$45^6 ≒83億$ということで全人口を上回るためこの仮説が考えられる。詳しい話はウィキペディアを見てください。
今回はこの仮説を応用すれば、平均の最短経路打数が求まるのではないかと思い、実際におまけコラムに書いてみました。式は以下を用います。
\log_{１記事の平均リンク数} 総記事数
結果は、4.477打(2026年7月時点)
5万回試行して求めた平均打数が4.043打であるため大体同じという！！
おわりに
気になった方はぜひ遊んでみてください。バグ報告やIssue、Starも大歓迎です。
- 🔗 サイトはこちら
- 🔗 GitHubリポジトリ