Pythonで幅優先探索（BFS）による最短経路のルートの復元方法

Aru

幅優先探索やダイクストラ法を使うと最短ルートの距離を求めることが可能です。距離ではなく、最短ルートそのものを知りたい場合もあるかと思います。この記事では最短ルートを求める（構成）する方法について解説します。

Contents

幅優先探索（BFS）で求めた経路を辿る
応用例
- AtCoder ABC405 D問題
まとめ

幅優先探索（BFS）で求めた経路を辿る

最短経路問題

縦H幅Wマスのグリッド上の迷路において、スタートからゴールまでの最短経路を求める問題があります。移動は、上下左右の壁でないマスへ移動できます。

マスの移動コストが１の場合、この問題は幅優先探索（BSF）を利用して簡単に解くことができます。

BSFの書き方についてはこちら

Pythonで深さ優先探索（DFS）,幅優先探索（BFS）,ダイクストラ法を実装する

BSFを実装する

例えば、以下のような迷路があるとします。

縦5, 幅10の迷路で、.は通路、#は壁、Sはスタート、Gはゴールを表しています。

5 10
..........
...#.###..
..##.....#
...####...
....S#G...

この迷路でスタートからゴールまでの距離を求めるプログラムは以下のようになります。

from collections import deque

h, w = map(int, input().split())
s = [input() for _ in range(h)]


sx, sy = 0,0
gx, gy = 0,0

for y in range(h) :
    for x  in range(w) :
        if s[y][x] == 'S' :
            sx, sy = x, y
        if s[y][x] == 'G' :
            gx, gy = x, y


# 幅優先探索
inf = int(1e9)
q = deque()
q.append((sx, sy))
dist = [[inf for _ in range (w)] for _ in range(h)]
dist[sy][sx] = 0

while q :
    x, y = q.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= w or ny < 0 or ny >= h :
            continue
        if s[ny][nx] == '#' :
            continue
        if dist[ny][nx] != inf :
            continue
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx, ny))

# 結果を表示
for e in dist:
    for v in e:
        if v == inf :
            print("  *", end=" ")
        else:
            print(f"{v:3}", end=" ")
    print()

print(f"dist = {dist[gy][gx]}")

このプログラムは、典型的な幅優先探索のコードです。結果は以下のようになります。

実行結果

  8   7   8   9  10  11  12  13  14  15 
  7   6   7   *  11   *   *   *  15  16 
  6   5   *   *  12  13  14  15  16   * 
  5   4   3   *   *   *   *  16  17  18 
  4   3   2   1   0   *  18  17  18  19 
dist = 18

前半の部分は、スタートから各マスへの距離です。スタートからゴールへの距離はdist=18と18マスが最短になります。

ここから、最短ルートを再構成してみます。

最短ルートを構成する

ルートの構成（復元）は、以下の手順で行います。

ゴールの位置をカレントのx,yとする（cx, cy）
ゴールの周辺４マスで、dist[cy][cx]-1の距離になるマスを見つけてcx, cyを更新する
スタートに到着するまで②を繰り返す

具体的には以下のようなコードになります。

最短ルートを再構成するコード

cy, cx = gy, gx
used = [[False for _ in range (w)] for _ in range(h)]
used[cy][cx] = True
route = [(cy+1, cx+1)]

while s[cy][cx] != 'S' :
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
        nx, ny = cx + dx, cy + dy
        if nx < 0 or nx >= w or ny < 0 or ny >= h :
            continue
        if s[ny][nx] == '#' :
            continue
        if dist[ny][nx] == inf :
            continue    
        if dist[ny][nx] == dist[cy][cx] - 1 :
            cx, cy = nx, ny
            route.append((cy+1, cx+1))
            used[cy][cx] = True
            break

コードは、先ほどの手順を実装しただけになります。なお、usedに通過したマスのグリッド情報を、routeに通過したマスの座標を記録しています。routeを逆順で辿れば、スタートからゴールまでに通過した経路になります。

コード全体

最短ルートを表示するコードの全体は以下のようになります。

from collections import deque

h, w = map(int, input().split())
s = [input() for _ in range(h)]


sx, sy = 0,0
gx, gy = 0,0

for y in range(h) :
    for x  in range(w) :
        if s[y][x] == 'S' :
            sx, sy = x, y
        if s[y][x] == 'G' :
            gx, gy = x, y


# 幅優先探索
inf = int(1e9)
q = deque()
q.append((sx, sy))
dist = [[inf for _ in range (w)] for _ in range(h)]
dist[sy][sx] = 0

while q :
    x, y = q.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= w or ny < 0 or ny >= h :
            continue
        if s[ny][nx] == '#' :
            continue
        if dist[ny][nx] != inf :
            continue
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx, ny))


cy, cx = gy, gx
used = [[False for _ in range (w)] for _ in range(h)]
used[cy][cx] = True
route = [(cy+1, cx+1)]

while s[cy][cx] != 'S' :
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
        nx, ny = cx + dx, cy + dy
        if nx < 0 or nx >= w or ny < 0 or ny >= h :
            continue
        if s[ny][nx] == '#' :
            continue
        if dist[ny][nx] == inf :
            continue    
        if dist[ny][nx] == dist[cy][cx] - 1 :
            cx, cy = nx, ny
            route.append((cy+1, cx+1))
            used[cy][cx] = True
            break


# 結果を表示
for e in dist:
    for v in e:
        if v == inf :
            print("  *", end=" ")
        else:
            print(f"{v:3}", end=" ")
    print()

# 結果を表示（道順）
for e in used:
    for v in e:
        if v :
            print("*", end="")
        else:
            print(f".", end="")
    print()

print(f"dist = {dist[gy][gx]}")
print(f"route = {route[::-1]}")

応用例

AtCoder ABC405 D問題

AtCoder Beginner Contest 405が、最短経路を可視化する問題でしたので、これを例に説明します。この問題では

各マスがスタートとなる
ゴール（E）が複数個存在する

という点で、先ほどの例とは異なります。しかしながら、以下のように考えることで最短経路問題になります。

ゴール（E）をスタートとして最短経路を求める

複数個のゴール（出口）をキューに登録してからBSFを開始すれば、いずれかの出口への最短経路が求まります。

上記のように考えれば、BSFを行って最短経路を求める問題に帰着できます。

あとは、再構成ですが、この問題では、「各マスについて、どちらに出口があるか」を求める問題なので、（自マスの距離−１）のマスの方向に矢印を配置すれば良いことになります。

気づいてしまえば、最短経路の再構成の問題と変わらないことがわかります。

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]


inf = int(1e9)
dist = [[inf] * W for _ in range(H)]
q = deque()
# ゴールを全て登録する
for i in range(H):
    for j in range(W):
        if grid[i][j] == 'E':
            dist[i][j] = 0
            q.append((j, i))

# BSF
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
    cx, cy = q.popleft()
    for dx, dy in dir:
        nx = cx + dx
        ny = cy + dy
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if grid[ny][nx] == '#':
            continue
        if dist[ny][nx] != inf:
            continue
        dist[ny][nx] = dist[cy][cx] + 1
        q.append((nx, ny))

# 出力を作成
result = []
for cy in range(H):
    row = []
    for cx in range(W):
        if grid[cy][cx] != '.':
            row.append(grid[cy][cx])
        else:
            current_d = dist[cy][cx]
            for dx, dy, d_char in [(-1, 0, '^'), (1, 0, 'v'), (0, -1, '<'), (0, 1, '>')]:
                ny = cy + dx
                nx = cx + dy
                if 0 <= ny < H and 0 <= nx < W:
                    if grid[ny][nx] != '#' and dist[ny][nx] == current_d - 1:
                        row.append(d_char)
                        break
    result.append(''.join(row))

for line in result:
    print(line)