Skip to content

Instantly share code, notes, and snippets.

@safhac
Last active December 26, 2021 07:44
Show Gist options
  • Save safhac/56e611bf57772a1699d73a44748ce0ad to your computer and use it in GitHub Desktop.
Save safhac/56e611bf57772a1699d73a44748ce0ad to your computer and use it in GitHub Desktop.
find shortest path in graph
import deque
graph2 = {
'Dov Aharon': ['Debbie Ben Zaken', 'Yaron Baberman'],
'Debbie Ben Zaken': [],
'Yaron Baberman': ['Dan Cohen'],
'Dan Cohen': ['David Dukovsky', 'Didi Eshkol'],
'David Dukovsky': [], 'Didi Eshkol': []
}
def find_path(graph, start, end):
path = {start: [start]}
queue = deque([start])
while len(queue):
at = queue.popleft()
for next in graph[at]:
if next not in path:
path[next] = [path[at], next]
queue.append(next)
return path.get(end)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment