Constructing the path

We have now seen the loop that is the essence of many graph search algorithms. But how do we find the shortest path? The loop doesn’t actually construct the paths; it only tells us how to visit everything on the map. That’s because Breadth First Search can be used for a lot more than just finding paths. Here though we want to use it for finding paths, so let’s modify the loop to keep track of where we came from for every location that’s visited, and rename visited to came_from:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

Now came_from for each location points to the place where we came from. That’s enough to reconstruct the entire path. Mouse over any location on the map and see how following the arrows gives you a reverse path back to the start position.

We’ve found paths from one location to all other locations. Often we don’t need all the paths; we only need a path from one location to one other location. We can stop expanding the frontier as soon as we’ve found our goal. Drag the X around see how the frontier stops expanding as soon as it reaches the X.

The code to reconstruct paths is simple: follow the arrows

current = goal
path = [current]
while current != start:
   current = came_from[current]
   path.append(current)
path.reverse()

That’s the simplest pathfinding algorithm. It works not only on grids as shown here but on any sort of graph structure.

The code is straightforward:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break           

   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current