Tushar Jain - 1 year ago 77

Python Question

I'm finding the shortest path using BFS, I get this

`RecursionError: maximum recursion depth exceeded in comparison`

Code below:

`def bfs_paths(graph, start, goal):`

queue = [(start, [start])]

while queue:

(vertex, path) = queue.pop(0)

for next in graph[vertex] - set(path):

if next == goal:

yield path + [next]

else:

queue.append((next, path + [next]))

def shortest_path(graph, start, goal):

try:

return next(bfs_paths(graph, start, goal))

except StopIteration:

return None

Usage example:

`graph = {'A': set(['B', 'C']),`

'B': set(['A', 'D', 'E']),

'C': set(['A', 'F']),

'D': set(['B']),

'E': set(['B', 'F']),

'F': set(['C', 'E'])}

shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']

Answer Source

Try this. It includes a visited set. I also modified the variable name 'next' to 'node' as it is a built in function

```
def bfs_paths(graph, start, goal):
visited = set()
queue = [(start, [start])]
while queue:
vertex, path = queue.pop(0)
visited.add(vertex)
for node in graph[vertex]:
if node in visited:
continue
elif node == goal:
yield path + [node]
else:
queue.append((node, path + [node]))
def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
```