BFS 最短経路長

BFS は 1 つの頂点からスタートし、隣接頂点へと徐々に探索を広げていくため、始点から他のすべての頂点までの最短経路を見つけることができます。これを実現するには、基本的なアルゴリズムに少し手を加える必要があります。ここでは、すべての要素が -1 に初期化された d という距離を管理する配列を用意します。d[i] が -1 の場合は、まだ未訪問であることを示します。正の値が入っていれば、スタート頂点からその頂点までの距離が格納されていることになります。

from collections import deque

n, e = map(int, input().split())        # n: vertices, e: edges
g = [[] for _ in range(n)]              # graph - adjacency list

for _ in range(e):                      # read edges
    a, b = map(int, input().split())    # a -> b and b -> a
    g[a].append(b)
    g[b].append(a)

start = int(input())                    # start vertex
d = [-1] * n                            # distance from start vertex
q = deque([start])                      # queue of vertices
d[start] = 0                            # distance from start to start is 0

while q:                                # while the queue is not empty
    v = q.popleft()                     # get vertex from queue
    print(v, end=' ')                   # print vertex
    for to in g[v]:                     # for each vertex connected to v
        if d[to] == -1:                 # if vertex is not visited
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            q.append(to)                # add vertex to queue

print(d)

ここではまず、全ての頂点の距離を示す配列 d を -1 に設定して初期化し、どの頂点もまだ訪問されていないことを示します。次に、d[start] を 0 に設定することで、スタート頂点からその頂点自身への距離が 0 であることを表しています。

アルゴリズムが頂点を処理する際、その頂点に対応する距離が d 配列で更新されていきます。こうして、スタート頂点から各頂点への距離情報をすべて得ることができます。

いくつかの入力例で、このアルゴリズムをシミュレーションしてみましょう。

n = 4, e = 4

The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]

The starting vertex is 3

d = [-1, -1, -1, 0], q = [3]

v = 3, q = [] → キューに未使用の隣接頂点を追加

d = [-1, -1, 1, 0], q = [2]

v = 2, q = [] → キューに未使用の隣接頂点を追加

d = [2, 2, 1, 0], q = [0, 1]

v = 0, q = [1] → キューに未使用の隣接頂点を追加

v = 1, q = [] → キューに未使用の隣接頂点を追加

終了

n = 5, e = 4

The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 4)]

The starting vertex is 0

d = [0, -1, -1, -1, -1], q = [0]

v = 0, q = [] → キューに未使用の隣接頂点を追加

d = [0, 1, 1, -1, -1], q = [1, 2]

v = 1, q = [2] → キューに未使用の隣接頂点を追加

v = 2, q = [] → キューに未使用の隣接頂点を追加

終了

Notice how nodes 3 and 4 were never visited.

They were not connected to the initial node 0.

チャレンジ: 最短経路長を求める

与えられた無向グラフにおいて、頂点 1 から頂点 v までの最短経路を計算するプログラムを作成してください。もしこれらの頂点が連結でない場合は、Impossible と出力してください。

入力

最初の行に、頂点数 v (1 ≤ v ≤ 100 000) と辺数 e (1 ≤ e ≤ 100 000) が与えられます。

続く e 行には、それぞれ 2 つの整数 v1, v2 (1 ≤ v1, v2 ≤ v) が書かれており、これは頂点 v1 と頂点 v2 が相互に接続されていることを表します。

出力

頂点 1 から頂点 v までの最短経路の長さを出力してください。もし連結でない場合は Impossible を出力します。

例

入力	出力
5 6 1 2 2 3 1 3 3 4 4 3 3 5	2
2 1 1 2	1
2 0	Impossible

チャレンジ: 最短経路長を求める

入力

出力

例

Constraints

To check your solution you need to sign in

Sign in to continue