Breadth first search all paths
- by Amndeep7
First of all, thank you for looking at this question.
For a school assignment we're supposed to create a BFS algorithm and use it to do various things. One of these things is that we're supposed to find all of the paths between the root and the goal nodes of a graph. I have no idea how to do this as I can't find a way to keep track of all of the alternate routes without also including copies/cycles.
Here is my BFS code:
def makePath(predecessors, last):
return makePath(predecessors, predecessors[last]) + [last] if last else []
def BFS1b(node, goal):
Q = [node]
predecessor = {node:None}
while Q:
current = Q.pop(0)
if current[0] == goal:
return makePath(predecessor, goal)
for subnode in graph[current[0]][2:]:
if subnode[0] not in predecessor:
predecessor[subnode[0]] = current[0]
Q.append(subnode[0])
A conceptual push in the right direction would be greatly appreciated.
tl;dr How do I use BFS to find all of the paths between two nodes?
