Skip to content

Instantly share code, notes, and snippets.

@Sahas-Ananth
Created March 27, 2021 18:16
Show Gist options
  • Save Sahas-Ananth/ac428fc6923b4f2ccfb18ccf4ef452a6 to your computer and use it in GitHub Desktop.
Save Sahas-Ananth/ac428fc6923b4f2ccfb18ccf4ef452a6 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
graph = {
"A": ["B", "C"],
"B": ["C", "D"],
"C": ["D"],
"D": ["C"],
"E": ["F"],
"F": ["C"],
}
def find_all_paths(start, end, path=[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
def shortest_path(all_paths):
return sorted(all_paths, key=len)[0]
def main():
avail_paths = find_all_paths("A", "C")
shrt_path = shortest_path(avail_paths[:])
print("All available Paths are: \n", avail_paths)
print("\nThe Shortest path is: \n", shrt_path)
if __name__ == "__main__":
try:
main()
except KeyboardInterrupt:
print("Closing program...")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment