Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
The implementation of breadth-first search that I converged to after X0 job interviews.
from typing import Dict, Set, Hashable
def shortest_path_bfs(graph: Dict[Hashable, Set[Hashable]] root: Hashable
) -> Dict[Hashable, int]:
"""Finds the shortest path between all nodes in |graph| time.
Args:
graph: A dict mapping nodes to connected nodes.
root: The node our search begins at.
Returns:
A dictionary containing the shortest paths from root to each node.
"""
queue = [root]
visited = set()
distances = {node: float("inf") for node in graph}
distances[root] = 0
while queue:
curr = queue.pop()
queue.extend(list(graph[curr] - visited))
for neighbour in graph[curr]:
distances[neighbour] = distances[curr] + 1
return distances
graph = {0: [1, 2, 3],
1: [0, 2],
2: [3],
3: []}
assert shortest_paths(graph, 0) == {0: 0, 1: 1, 2: 1, 3: 1}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment