Shortest Path BFS

In unweighted graphs, BFS gives shortest path.

Example graph

graph = {
  "A": ["B", "C"],
  "B": ["D"],
  "C": ["D"],
  "D": []
}

BFS shortest path

from collections import deque

def shortest(graph, start):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, dist = q.popleft()
        if node == "D":
            return dist
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                q.append((nxt, dist+1))

print(shortest(graph, "A"))  # 2

Graph

flowchart LR
  A --> B
  A --> C
  B --> D
  C --> D

Remember

• BFS = shortest in unweighted graphs
• uses queue