BFS で最短経路の長さを求める｜コードで実践

BFS で最短経路の長さを求める

このレッスンで分かること

重みなしなら BFS、重みありなら Dijkstra

O(n + m)

BFS が最短経路問題に強い理由は、「距離が短いノードから順に展開する」という性質にあります

BFS で最短経路の長さを求めるとは

重みなし無向グラフで、BFS を使って始点から終点までの最短経路 (辺数) を求める関数を実装する。本レッスンでは、BFS で最短経路の長さを求めるの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

BFS が最短経路問題に強い理由は、「距離が短いノードから順に展開する」という性質にあります。重みのないグラフ (すべての辺の重みが 1 と等しい) では、BFS でノードを訪問した順番がそのまま 始点からの最短距離 に対応します。これは Dijkstra や A* といった重み付き最短経路アルゴリズムの基礎にあたる考え方です。

本レッスンでは、ノード数 n、無向エッジリスト edges、始点 s、終点 t を受け取り、s から t への最短経路の 辺の本数 を返す shortestPath(n, edges, s, t) を実装します。到達できないときは -1 を返します。

「重みなしの最短経路」は BFS で O(n + m)。重みありなら Dijkstra（優先度付きキュー）を使う。BFS は O(n + m) だが Dijkstra は O((n + m) log n) であり、辺重みがすべて等しいなら BFS の方が高速。

距離レベルでまとめて訪問する

BFS は「現在のフロンティア (同じ距離のノード群)」を一気に展開してから次のレベルに進むのが特徴です。実装上は キューに距離も一緒に乗せる か、level by level に処理する の 2 パターンがあります。本レッスンでは前者を採用します。

diagram (will load when visible)

図のポイント (テキスト併記)

上の例だと s=0 から t=4 への最短距離は 3 (辺 3 本)

上の例だと s=0 から t=4 への最短距離は 3 (辺 3 本)。0 -> 1 -> 3 -> 4 でも 0 -> 2 -> 3 -> 4 でも、最短は同じ長さです。

Python での実装

Python

from collections import deque

def shortestPath(n, edges, s, t):
    if s == t:
        return 0
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n
    visited[s] = True
    queue = deque([(s, 0)])
    while queue:
        u, d = queue.popleft()
        for v in adj[u]:
            if v == t:
                return d + 1
            if not visited[v]:
                visited[v] = True
                queue.append((v, d + 1))
    return -1

キューに (ノード, 距離) のタプルを乗せ、隣接ノードへは d + 1 で渡します。v == t の判定をキュー追加より前に行うと、最初の到達時 = 最短経路を確実に拾えます。

JavaScript での実装

JavaScript

function shortestPath(n, edges, s, t) {
  if (s === t) return 0;
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Array(n).fill(false);
  visited[s] = true;
  const queue = [[s, 0]];
  let head = 0;
  while (head < queue.length) {
    const [u, d] = queue[head++];
    for (const v of adj[u]) {
      if (v === t) return d + 1;
      if (!visited[v]) {
        visited[v] = true;
        queue.push([v, d + 1]);
      }
    }
  }
  return -1;
}

配列を擬似キューとして使い、shift() を避けて head インデックスを進めます。大規模グラフでも安定して動きます。

なぜ BFS で最短経路が求まるのか

重要なポイントは「BFS では、距離が短いノードが必ず先に visited になる」ことです。あるノード v が d 歩で到達できる場所なら、d-1 歩で到達できるノードの隣接として d のタイミングでマークされ、それより遅れて再訪することはありません。重みがすべて 1 だから成り立つ性質で、重みが違うと Dijkstra が必要になります。

計算量

O(n + m)。BFS の標準的なコストです。重み付き Dijkstra は O((n + m) log n) なので、辺重みがすべて等しいなら BFS の方が速いです。

重みなしなら BFS、重みありなら Dijkstra。これが鉄則。

よくある間違い

1 つ目は キューに入れるタイミング で距離を計算し忘れるパターン。d + 1 を渡し忘れて、いつまでも d が増えない実装になりがち。2 つ目は s == t の最初の判定漏れで、0 ではなく 1 を返してしまうケース。3 つ目は visited を「キューから取り出すとき」に立ててしまい、同じノードが複数回キューに入って距離がおかしくなる現象。キューに入れる瞬間 にマークするのが鉄則です。

やってみよう

n=5, edges=[[0,1],[0,2],[1,3],[2,3],[3,4]], s=0, t=4 で 3 が返ること。
到達不能な t で -1 が返ること。
s == t で 0 が返ること。

BFS で最短経路が出せると、迷路の最短手数や Word Ladder 系の問題が一気に解けるようになる。

よくある質問

Q. BFS と DFS はどう使い分けますか？

A. 最短経路（最小ステップ数）が欲しいなら BFS、全探索やバックトラックなら DFS が向きます。BFS は queue、DFS は stack や再帰で実装します。グラフのサイズが大きい場合は BFS の方がメモリ使用量が増えがちです。

Q. 重み付きグラフの最短経路は BFS で良いですか？

A. 辺の重みが全て同じなら BFS で十分です。異なる重みがあるならダイクストラ法（優先度付きキュー）を使ってください。負の重みを許すならベルマンフォード、全頂点ペアならフロイド-ワーシャル法と、用途で使い分けます。

Q. 訪問済みの管理はどうすれば良い？

A. Set や boolean[] で「訪れた」フラグを管理するのが定石です。BFS では queue に入れた時点でフラグを立てるのがコツで、取り出した時点で立てると同じノードが複数回 queue に入り処理が膨らみます。

次のレッスン

次は トポロジカルソート で、有向非巡回グラフ (DAG) の頂点を依存関係の順に並べる方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

最短経路 BFS の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 最短経路 BFS とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

BFS で最短経路の長さを求める