Breadth first search all paths

Question

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?

Here is the graph as I'm not sure how to answer Jeff Marcado's question.

graph = {   'A':[366, 3,    ('Z',   75 ), ('T', 118), ('S', 140)],
            'Z':[374, 2,    ('A',   75 ), ('O', 71 )],
            'T':[329, 2,    ('A',   118), ('L', 111)],
            'L':[244, 2,    ('T',   111), ('M', 70 )],
            'M':[241, 2,    ('L',   70 ), ('D', 75 )],
            'D':[242, 2,    ('M',   75 ), ('C', 120)],
            'C':[160, 3,    ('D',   120), ('R', 146), ('P', 138)],
            'R':[193, 3,    ('C',   146), ('P', 97 ), ('S', 80 )],
            'S':[253, 4,    ('R',   80 ), ('F', 99 ), ('O', 151), ('A', 140)],
            'O':[380, 2,    ('S',   151), ('Z', 71 )],
            'P':[100, 3,    ('C',   138), ('R', 97 ), ('B', 101)],
            'F':[176, 2,    ('S',   99 ), ('B', 211)],
            'B':[  0, 4,    ('P',   101), ('F', 211), ('G', 90 ), ('U', 85 )],
            'G':[ 77, 1,    ('B',   90 )],
            'U':[ 80, 3,    ('B',   85 ), ('H', 98 ), ('V', 142)],
            'H':[151, 2,    ('U',   98 ), ('E', 86 )],
            'E':[161, 1,    ('H',   86 )],
            'V':[199, 2,    ('U',   142), ('I', 92 )],
            'I':[226, 2,    ('V',   92 ), ('N', 87 )],
            'N':[243, 1,    ('I',   87 )],
            'W':[400, 1,    ('X',   100)],
            'X':[400, 1,    ('W',   100)],}

@JeffMercado We haven't covered these distinctions yet, I have shown the graph we have to use, if that helps. — Amndeep7
You need to split up the work into separate functions. I would create functions to get the next nodes, remove edges you've used up, and return paths. — kreativitea
@Amndeep7: please read the homework tag wiki. If it's homework or you only want directions rather than code, state that in your question. Don't use the homework tag. — Mat
@Mat : Thank you for informing me about the state of the homework tag, I will make sure not to use it anymore. — Amndeep7

Maxime Chéramy Maxime Chéramy · Accepted Answer · 2012-11-01T09:21:59

Firstly, your algorithm should not return when you reach the goal node otherwise you'll have only one solution. Instead, you should use a list to store the various solutions.

Regarding the core of the algorithm, keep in mind that a BFS-search will not explore one path at a time but all. So you cannot just store one node in your queue but rather a path.

Then you simply check if the next node is not already in your current path to add it to avoid cycles. If the last node of the current path is the goal node, append it to the solution list.

Finally, when there is no more incomplete path in the queue (== the queue is empty), return the solution list.

Breadth first search all paths

1 Answers