双方向 BFS

01 / 一文で言うと

両端から同時に BFS を走らせる。両側のフロンティアが触れた瞬間に最短路が得られる。 利得は深さに対して指数的:O(b^d) が O(b^(d/2)) になる —— ソースとターゲットの両方が既知なら有効。
問題無重みグラフのソースからターゲットへの最短路長入力graph=mesh, A → F
AS:0BCDEFT:0
A(正方向)と F(逆方向)から同時に BFS。distS[A] = 0、distT[F] = 0 で初期化、両端のフロンティアは種 1 つずつ。
ステップ
0 / 19
フロンティア |S|, |T|
1, 1
訪問済
1 + 1
路長
—
0 / 19

02 / パターンの骨格

# 層を 1 つずつ進める双方向 BFSdistS ← { s: 0 }; distT ← { t: 0 }frontS ← {s}; frontT ← {t}while frontS と frontT がともに空でない:if |frontS| ≤ |frontT|: frontS を distT に対して展開else: frontT を distS に対して展開for u in front for v in adj[u]:if v が反対側にある: return same[u] + other[v] + 1if v が同じ側にない: same[v] = same[u] + 1; nextFront ← vreturn −1 # 非連結

03 / このパターンを使うべき合図

「最短変換 / 突然変異」
ワードラダー、遺伝子突然変異、ダイヤルロック —— 始端と終端が具体状態で、辺コストが均等(1 ホップ = 1 変換)の状態空間探索。
「両端点が既知」
ターゲットが具体的なときのみ意味がある。 一対多最短路(Dijkstra、ソース BFS)では片側 BFS で十分(漸近同等)。
「分岐因子が大きすぎて BFS が手に負えない」
ワードラダーで 26 文字 × L 位置、4 桁ダイヤルロックで 10 数字 —— 分岐因子 b が大きく見える。双方向 BFS は深さを半分にし、b^(d/2) なら扱いやすい。
「無重みグラフの最短路」
無重みなら BFS が最短;双方向はその上の最適化。 重み付きなら双方向 Dijkstra(高度・面接ではまれ)。

04 / よくある落とし穴

先に大きい方のフロンティアを展開してしまう。
要点は両側のフロンティアを均衡させること —— 常に小さい方を先に展開する。 先に到着した方をずっと展開すると、片側が爆発して加速が消える。
反対側を更新後に確認、前ではなく。
「出会い」判定は隣人を調べるたびに行う —— 自分の訪問集合に加える前に反対側を見る。 そうしないと最初の出会いを逃し、真の最短より長い路を返してしまう。
答えの式を逆に書く。
辺 u → v で出会ったとき(u は現在の側、v は反対側で訪問済)、 答えは distSide[u] + distOther[v] + 1 —— +1 はその橋辺自身。 オフ・バイ・ワンは典型的バグ。
最初の出会いを最短だと決めつける。
同じ層を展開しているとき、複数の出会い候補が現れることがある —— 路再構成が必要なら層を全部処理してから結論を出す。 そうでなければ BFS の不変量で「その深さでの最初の出会い」が最短。

05 / LeetCode で練習

中級10

01Minimum Genetic Mutation— LC 433→0201 Matrix— LC 542→03Open the Lock— LC 752→04Rotting Oranges— LC 994→05Shortest Path in Binary Matrix— LC 1091→06As Far from Land as Possible— LC 1162→07Jump Game III— LC 1306→08Get Watched Videos by Your Friends— LC 1311→09Minimum Jumps to Reach Home— LC 1654→10Shortest Path to Get Food— LC 1730→

難しい9

01Word Ladder II— LC 126→02Word Ladder— LC 127→03Cut Off Trees for Golf Event— LC 675→04Sliding Puzzle— LC 773→05Bus Routes— LC 815→06K-Similar Strings— LC 854→07Shortest Path to Get All Keys— LC 864→08Minimum Number of Flips to Convert Binary Matrix to Zero Matrix— LC 1284→09Shortest Path in a Grid with Obstacles Elimination— LC 1293→