Created
May 21, 2017 16:31
-
-
Save ashkanRmk/a96698e3bf4a651daa674c32e4e8c3ac to your computer and use it in GitHub Desktop.
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
graph = {'A': ['B', 'C'], | |
'B': ['C', 'D'], | |
'C': ['D'], | |
'D': ['C'], | |
'E': ['F'], | |
'F': ['C']} | |
def find_shortest_path(graph, start, end, path=[]): | |
path = path + [start] | |
if start == end: | |
return path | |
if start not in graph: | |
return None | |
shortest = None | |
for node in graph[start]: | |
if node not in path: | |
newpath = find_shortest_path(graph, node, end, path) | |
if newpath: | |
if not shortest or len(newpath) < len(shortest): | |
shortest = newpath | |
return shortest | |
def find_all_paths(graph, start, end, path=[]): | |
path = path + [start] | |
if start == end: | |
return [path] | |
if start not in graph: | |
return [] | |
paths = [] | |
for node in graph[start]: | |
if node not in path: | |
newpaths = find_all_paths(graph, node, end, path) | |
for newpath in newpaths: | |
paths.append(newpath) | |
return paths | |
print(find_shortest_path(graph, 'A', 'D')) | |
print(find_all_paths(graph, 'A', 'D')) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment