最短パスを復元する

グラフ上の最短パスを求めるとき、最後にパスそのものを復元することもできます。

そのためには、訪れた各頂点について「親（parent）」となる頂点を記録しておきます。たとえば、頂点 v を処理して頂点 to をキューに追加したら、「to の親は v」であると記録するわけです。こうしておけば、最後にゴールからスタートまで親をたどる形でパスを復元できます。具体的には、パスの終点から始めて、その親をたどり、さらにその親…というふうに進み、親が存在しなくなる頂点（スタート地点）に到達するまでたどっていきます。最後に、そのたどった順序を反転すればスタートからゴールへ向かう道筋が得られます。これは次のように、追加で親の配列 p を持つことで実装できます。

start = int(input())                    # スタート頂点
d = [-1] * n                            # start からの距離
p = [-1] * n                            # 親頂点
q = deque([start])                      # 頂点を管理するキュー
d[start] = 0                            # start から start への距離は 0

while q:                                # キューが空でないうちは処理を続行
    v = q.popleft()                     # キューから頂点を取り出す
    print(v, end=' ')                   # 頂点を出力（確認用）
    for to in g[v]:                     # v に隣接する頂点を順番にチェック
        if d[to] == -1:                 # まだ訪れていない頂点の場合
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            p[to] = v                   # to の親として v を記録
            q.append(to)                # to をキューに追加

# start から end へのパスを復元
end = int(input())                      # ゴール頂点
path = []                               # start から end への経路
while end != -1:                        # 親が無くなるまでたどる
    path.append(end)                    # パスに頂点を追加
    end = p[end]                        # 親頂点へ移動

print(*path[::-1], sep=' -> ')          # 逆順に並べてパスを出力

このように、各要素をキューに追加すると同時にその “親” となる頂点を記録し、最後に「ゴールからスタートへ向かって」親をたどりながらパスを復元します。最終的には、復元したリストがゴールからスタートの順番で並ぶため、逆順にして出力することでスタートからゴールの順番で表示されます。

次に、このアルゴリズムを具体的な入力例でシミュレーションしてみましょう。

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 and the end vertex is 0

p = [-1, -1, -1, -1], q = [3]

v = 3, q = [] → まだ使われていない隣接頂点をキューに追加

p = [-1, -1, 3, -1], q = [2]

v = 2, q = [] → まだ使われていない隣接頂点をキューに追加

p = [2, 2, 3, -1], q = [0, 1]

v = 0, q = [1] → まだ使われていない隣接頂点をキューに追加

v = 1, q = [] → まだ使われていない隣接頂点をキューに追加

パスを復元

end = 0 → end = 2 → end = 3

print 3 → 2 → 0

なお、アルゴリズム終了時点で d[end] が -1 のままであれば、end 頂点には到達できなかったことを意味します。

チャレンジ：最短ルートを見つけよう

インターネットは互いに接続されたコンピュータの集合で、データをやり取りすることができます。ここでは、コンピュータが 1 から n までの番号で管理されており、どのコンピュータ同士が接続されているかが分かっている状況を考えます。アリスは自分のメッセージをボブに送りたいと思っており、その際できる限り速く届けたい（つまり経路はできるだけ短いほうがよい）と考えています。

アリスのコンピュータ番号を a、ボブのコンピュータ番号を b とするとき、メッセージを最短時間で届けるためのコンピュータの並び（経路）を求めてください。

入力

最初の行には、ネットワーク上のコンピュータの数 n (1 ≤ n ≤ 100 000) と、接続の数 e (1 ≤ e ≤ 100 000) が与えられます。

次の行では、アリスとボブのコンピュータ番号 a と b (1 ≤ a, b ≤ n) が与えられます。

続く e 行には、コンピュータ同士の接続を示す整数 c1、c2 (1 ≤ c1, c2 ≤ n) のペアが与えられ、c1 と c2 は双方向でつながっていることを意味します。

出力

最短時間でメッセージを届けるために通過するコンピュータの番号を順番に出力してください。番号同士はスペースで区切ってください。最短経路が複数ある場合、いずれの経路を出力してもかまいません。

例

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

チャレンジ：最短ルートを見つけよう

入力

出力

例

Constraints

To check your solution you need to sign in

Sign in to continue