1. Bugs
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 thedict.update
method.But what are you trying to do here anyway? If you're trying to copy
path_holder
intodct
, you could just write:dct = dict(path_holder)
but why bother making a copy? Why not just use
path_holder
?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.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)
afterpath.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 tonode4
, but there is no route fromnode4
toGOAL
except for the one that goes throughnode3
. And the search will never consider addingnode3
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:
Your variable
path_holder
contains a data structure that is known as a graph in adjacency list representation. So I have called this variablegraph
.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.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.