Medium Queue + Visited Graphs
In plain English: Find the fewest edges to get from a starting node to every other node in an unweighted graph.
BFS explores all nodes at distance d before d+1 — the first time you reach any node is guaranteed to be the shortest path.
Prompt
Find shortest distances from a start node in an unweighted graph.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def bfs_dist(graph, start):
dist = {start: 0}
q = deque([start])
while q:
node = q.popleft()
for nb in graph[node]:
if nb not in dist:
dist[nb] = dist[node] + 1 # first visit = shortest distance
q.append(nb)
return dist
# Test: bfs_dist({0:[1,2], 1:[0,3], 2:[0], 3:[1]}, 0)
# => {0:0, 1:1, 2:1, 3:2}