問題
次のような重みなし無向グラフに対して、頂点1から各頂点までの最短経路長を求めて下さい。
🔹頂点数は N、辺の数は M
🔹結びつく2つの頂点はリスト型に格納(edges変数)
[制約]
🔹1≦N≦100000
🔹0≦M≦min(100000,N(N−1)/2)
🔹1≦Ai<Bi≦N
解き方・ソースコード
この問題を幅優先探索で解いてきます。
幅優先探索は、スタートに近い頂点から順番に探索していくアルゴリズムです。
今回は、キューを使った方法で幅優先探索を行います。
手順は以下の通りです。
手順1:頂点 1 から頂点 x までの最短経路長の確定値を、dist[x]=−1 に初期化する。
手順2:キューに頂点 1 を追加し、dist[1]=0 にする。
手順3:キューが空になるまで、以下の手続きを繰り返す。
🔹キューの先頭要素 pos を取得し、それをキューから削除する。
🔹pos と隣接するすべての未確定頂点 to に対し、dist[to]=dist[pos]+1 を設定し、キューに to を追加する。
(未確定頂点とは dist[x]=−1 となっている頂点のことです。)
[Google Colaboratory]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| N = 6 M = 5
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 6)]
from collections import deque
G = [ list() for i in range(N + 1) ] for a, b in edges: G[a].append(b) G[b].append(a)
dist = [-1] * (N + 1) dist[1] = 0 Q = deque() Q.append(1)
while len(Q) > 0: pos = Q.popleft() for nex in G[pos]: if dist[nex] == -1: dist[nex] = dist[pos] + 1 Q.append(nex)
for i in range(1, N + 1): print('頂点 1 から頂点 {} までの最短経路は {}'.format(i, dist[i]))
|
[実行結果(入力例1)]
頂点 1 から頂点 1 までの最短経路は 0
頂点 1 から頂点 2 までの最短経路は 1
頂点 1 から頂点 3 までの最短経路は 1
頂点 1 から頂点 4 までの最短経路は 2
頂点 1 から頂点 5 までの最短経路は -1
頂点 1 から頂点 6 までの最短経路は 3
頂点1から各頂点への最短経路長を求めることができました。