FilesExpand file tree

master

/

find_path.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (49 loc) · 1.46 KB

master

/

find_path.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (49 loc) · 1.46 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

myGraph = {'A': ['B', 'C'],

'B': ['C', 'D'],

'C': ['D', 'F'],

'D': ['C'],

'E': ['F'],

'F': ['C']}

# find path from start to end using recursion with backtracking

def find_path(graph, start, end, path=[]):

path = path + [start]

if (start == end):

return path

if not start in graph:

return None

for node in graph[start]:

if node not in path:

newpath = find_path(graph, node, end, path)

return newpath

return None

# find all path

def find_all_path(graph, start, end, path=[]):

path = path + [start]

print(path)

if (start == end):

return [path]

if not start in graph:

return None

paths = []

for node in graph[start]:

if node not in path:

newpaths = find_all_path(graph, node, end, path)

for newpath in newpaths:

paths.append(newpath)

return paths

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, start, end, path)

if newpath:

if not shortest or len(newpath) < len(shortest):

shortest = newpath

return shortest

print(find_all_path(myGraph, 'A', 'F'))

# print(find_shortest_path(myGraph, 'A', 'D'))