BFSで重みなし最短路

辺を1本通るコストがすべて同じなら、近い頂点から順番に調べます。キューは先に入れたものから取り出します。

言語：Python / 計算量：O(V+E)

前提：DPは「同じ続きをまとめる」

考え方

1. 距離 -1 を未訪問とします。
2. 始点の距離を0にしてキューへ。
3. 未訪問の隣へ距離+1を付け、キューに追加します。

具体例

0—1—2 なら0からの距離は[0,1,2]。初めて発見した経路が最短です。

実装

from collections import deque
g = [[1],[0,2],[1]]
d = [-1] * 3
d[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for u in g[v]:
        if d[u] == -1:
            d[u] = d[v] + 1
            q.append(u)
print(d)

注意する条件

キューに追加するときに訪問済みにします。取り出した後にすると同じ頂点が何度も入ります。

確認問題

0—1—2—3 の0から3への距離は？

実装課題

N M、続いて M 本の無向辺 u v（0始まり）。頂点0からN-1への最短辺数。到達不能は-1。N,M ≤ 200000、N ≥ 1。

入力:
3 2
0 1
1 2
出力:
2

from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int,input().split())
    g[u].append(v); g[v].append(u)
d = [-1]*n; d[0]=0
q = deque([0])
while q:
    v=q.popleft()
    for u in g[v]:
        if d[u] == -1:
            d[u]=d[v]+1
            q.append(u)
print(d[-1])

読了の記録・下書き・メモへ