Shortest path with BFS output graph

1. Bugs

1. When I run your code I get the following error:

   >>> backtrace(path_holder, 'node1', 'GOAL')
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "q20349609.py", line 13, in backtrace
       dct.update(d)
   ValueError: dictionary update sequence element #0 has length 1; 2 is required
   

   That's because when you iterate over a dictionary like this:

   for d in path_holder:
   

   what you get are the keys of the dictionary. So d takes values 'node1', 'node2' and so on, and you can't pass these to the dict.update method.

   But what are you trying to do here anyway? If you're trying to copy path_holder into dct, you could just write:

   dct = dict(path_holder)
   

   but why bother making a copy? Why not just use path_holder?

2. With bug #1 fixed, the program runs but get stuck in an infinite loop. That's because of these lines:

   if j not in path:
       if j == goal:
           path.append(i)
   

   These lines mean that you only add a node to the path if it has a neighbour j which is not yet in the path, but is equal to the goal. But hang on a second, goal is already in the path at this point. So both conditions cannot be satisfied at the same time. Hence nothing ever gets added to the path!

   Clearly the line:

   if j not in path:
   

   should be:

   if i not in path:
   

   since i is the node we are considering adding to the path.

3. With bugs #1 and #2 fixed, the program makes some progress but still gets stuck in an infinite loop. If we add the line print(path) after path.append(i) then we get the following output up to the point where it gets stuck:

   >>> backtrace(path_holder, 'node1', 'GOAL')
   ['GOAL', 'node6']
   ['GOAL', 'node6', 'node3']
   ['GOAL', 'node6', 'node3', 'node4']
   

   You can see that the search has made a mistake: from node3 it has gone to node4, but there is no route from node4 to GOAL except for the one that goes through node3. And the search will never consider adding node3 to the path, because it's already there.

2. What to do instead

When you find a path to a node like node4, you can't know whether or not that node will be on the shortest path from GOAL to node1. All you can know at this point is that if node4 is on the shortest path from GOAL to node1, then you'll get there via node3. So that's all that you must record.

Here's how I'd implement this, using the dictionary visited to record for each node the previous node on the shortest path from start to that node, and a collections.deque to maintain a queue of nodes whose neighbours we may not have visited yet.

from collections import deque

class NotFound(Exception): pass

def search(graph, start, goal):
    """Find the shortest path from start to goal in graph (which must be a
    map from a node to an iterable of adjacent nodes), using
    breadth-first search.

        >>> graph = {
        ...     1: [2, 4, 5],  
        ...     2: [1],
        ...     3: [4, 6],
        ...     4: [2, 1, 3],
        ...     5: [],
        ...     6: [7],
        ...     7: [],
        ... }
        >>> search(graph, 1, 7)
        [1, 4, 3, 6, 7]
        >>> search(graph, 1, 1)
        [1]
        >>> search(graph, 5, 1) # doctest: +IGNORE_EXCEPTION_DETAIL
        Traceback (most recent call last):
            ...
        NotFound: No path from 5 to 1

    """
    visited = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = visited[node]
            return path[::-1]
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited[neighbour] = node
                queue.append(neighbour)
    raise NotFound('No path from {} to {}'.format(start, goal))

Notes:

1. Your variable path_holder contains a data structure that is known as a graph in adjacency list representation. So I have called this variable graph.

2. I've written a docstring explaining what the function does and how to call it. The docstring also contains embedded code examples that can be run using the doctest module.

3. Your function searches backwards from the goal to the start. But this is just the same as searching forwards from the start to the goal with all the edges reversed. So I've kept things simple by searching forwards.