Created
April 7, 2018 18:56
-
-
Save finbarrtimbers/afcbd0900a13a3af5e3ac0eabbe48511 to your computer and use it in GitHub Desktop.
The implementation of breadth-first search that I converged to after X0 job interviews.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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