BFS で最短経路の長さを求める
着けるのは分かった。では何歩か
前のレッスンで「たどり着けるか」は答えられるようになりました。次は「何歩で着くか」です。乗り換えの回数、迷路の最短手数、SNS で何人を介してつながっているか。どれも同じ問いです。
歩数を答えるには、探索の途中で「今、起点から何歩の場所にいるか」を持ち歩く必要があります。ただし持ち歩くだけでは足りません。最初に見つけた道が最短だと言い切れる 探索でなければ、たまたま先に見つかった遠回りを答えてしまいます。
深く潜ると、遠回りを先に見つける
0-1、1-2、2-3、0-3 の 4 本の辺を考えます。0 から 3 へは、辺 1 本で行けます。
ところが深さ優先で歩くと、0 の隣として先に 1 を選んだ場合、1 から 2、2 から 3 と潜って 3 歩で到着します。最初に着いた道が 3 歩なので、そのまま答えると間違いです。正しい答えを出すには、残りの道も全部たどって一番短いものを選び直すことになります。
幅優先ならこうなりません。0 の隣は 1 と 3 の 2 つで、どちらも「1 歩の場所」としてまとめて先に処理されます。2 歩の場所へ進むのは、1 歩の場所を全部見終わったあとです。
近い場所から順に、取りこぼさず処理する。だから 最初に目的地に触れたときの歩数が、そのまま最小 になります。これは辺 1 本の重みがどれも等しいから成り立つ話です。辺に距離や料金が付くと、辺の本数が少ない道が一番安いとは限らなくなり、この理屈は使えません。
1 段ずつ進める
歩数を持ち歩く書き方は 2 通りあります。キューに「点と歩数」の組を入れるか、同じ歩数の点をひとまとまりにして 1 段ずつ進めるかです。後者は形が見えやすいので、別の題材で見てみます。2 歩以内で届く人を集める処理です。
Python
def within_two(graph, start):
seen = {start}
frontier = [start]
for step in range(2):
next_frontier = []
for person in frontier:
for other in graph[person]:
if other not in seen:
seen.add(other)
next_frontier.append(other)
frontier = next_frontier
return seenfrontier が「ちょうど今の歩数で届く人たち」です。ループを 1 周すると、まとめて 1 歩ぶん外へ広がります。目的地が next_frontier に入った周回の番号が、そのまま最短の歩数です。
課題では歩数の上限がないので、目的地に触れるか、広げる先が無くなるまで回します。無くなったということは、どう歩いても届かないということなので、その場合は -1 を返します。
出発点と目的地が同じなら 0 歩です。前のレッスンと同じく、探索を始める前に返してしまいます。
やってみよう
edges=[[0,1],[0,2],[1,3],[2,3],[3,4]]で 0 から 4 は 3 歩。0-1-3-4 でも 0-2-3-4 でも同じ長さ- 別の塊にある点を目的地にすると -1 になる
- 三角形
[[0,1],[1,2],[2,0]]で 0 から 2 は 1 歩。遠回りの 2 歩に引きずられないことを確かめる
要件
- BFS を使うこと (DFS は最短保証なし)
- 到達できない場合は -1 を返すこと
- s == t のときは 0 を返すこと
入出力例
shortestPath(4, [[0,1],[1,2],[2,3]], 0, 3) → 3
shortestPath(5, [[0,1],[0,2],[1,3],[2,3],[3,4]], 0, 4) → 3
shortestPath(3, [], 1, 1) → 0
shortestPath(5, [[0,1],[2,3]], 0, 3) → -1
shortestPath(3, [[0,1],[1,2],[2,0]], 0, 2) → 1
shortestPath(6, [[0,1],[1,2],[2,3],[3,1],[3,4],[4,5]], 0, 5) → 4ヒント
