中文
devexamples

Breadth-First Shortest Path in a Graph

Find the fewest hops between two nodes with breadth-first search, reconstructing the path and reporting when no route exists.

PythonData Integrity

Code

snippet
from collections import deque
from typing import Dict, List, Optional


def shortest_path(
    graph: Dict[str, List[str]], start: str, goal: str
) -> Optional[List[str]]:
    if start == goal:
        return [start]
    queue = deque([start])
    parents: Dict[str, Optional[str]] = {start: None}
    while queue:
        node = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor in parents:
                continue
            parents[neighbor] = node
            if neighbor == goal:
                return reconstruct(parents, goal)
            queue.append(neighbor)
    return None


def reconstruct(parents: Dict[str, Optional[str]], goal: str) -> List[str]:
    path = [goal]
    while parents[path[-1]] is not None:
        path.append(parents[path[-1]])
    return list(reversed(path))

Related Examples