Graph Theory | BFS Shortest Path Problem on a Grid

Graph Theory | BFS Shortest Path Problem on a Grid

Hi all, welcome back to another post of my brand new series on Graph Theory named Graph Theory: Go Hero . I undoubtedly recommend the complete series, if you are planning to get started with or want to have a quick refresher. We’re going to see how we can use Breadth First Search ( BFS ) to solve a shortest path problem. I have already done an another post on BFS , earlier. So, let’s dive into deep.

I hope you have an idea about what is Breadth First Search ( BFS ) and how it works, because we would be using the BFS concepts intensively.

Setting the Scene

Many problems in Graph Theory could be represented using grids, because interestingly grids are a form of implicit graph. We can determine the neighbors of our current location by searching with in the grid. A type of problem where we find a shortest path in a grid is solving a maze like below.

Another example could be routing through obstacles (like trees, rivers, rocks etc) to get to a location.

Graph Theory on Grids

A common approach to solve graph problems is to first convert the structure into some representational formats like adjacency matrix or list. Basically these are data structures which store the neighborhood information with in the graph. Let’s see a more intuitive version of it.

Consider we have an imaginary graph.

No, this is not a graph. Look at the figure 1, but that’s what I was talking about. Imagine that, every cell in figure 1 has neighbors to it’s left, right, bottom and up. For more clarity, cell 0 has two neighbors, 1 and 2. In the same way cell 4 also has two neighbors 2 and 3. We can review these cells as the vertices in a graph where rows * columns would be the total number of vertices. Figure 2 is the adjacency list representing our imaginary graph, now you can relate it with the first figure, right? The last figure depicts the adjacency matrix of the same graph. Every cell (i, j) of adjacency matrix is filled with 1s where nodes i and j have an edge in between them. We used just 1s and 0s here, because we have no information about the cost from vertex i to j. If we had that, we could have used that information, as well.

Once we have an adjacency list / matrix representation of a graph, we can run multiple graph algorithms on top it to solve different usecases like finding shortest path and connected components.

Dungeon Problem

This is probably a problem statement we have encountered in many interviews and programming competitions and it goes as follows.

Suppose you are trapped in a 2D dungeon and you have to find the easiest way out. Hold on, we have some obstacles too. The dungeon is composed of unit cubes which may or may not be filled with rocks. It would take exactly one minute to move either east, west, south or north. You can’t move diagonally as the maze is tightly packed with solid rocks.

The dungeon has a size of R x C where R is number of rows and c is number of columns. We have to start at cell ‘S’ and we have an exit at cell ‘E’. The number ( # ) symbol depicts the road blocks in the route and period ( . ) shows an open route.

In the given setup, one solution could be drawn as above in the green route. Our approach is to do a BFS starting from the cell S , until we find the exit cell E.

If you remember , we used a queue to store the points to be visited later in the graph. We use the same here too. We start from cell (0,0) and add it to our queue. Once it’s visited we add all the neighbors of the visited cell to the queue. Cell (0,0) has two neighbors, (0,1) and (1,0). The queue becomes bigger and bigger as we visit and add more neighbors into the queue, iteratively. We stop this process when we meet the exit condition i.e. we visit the exit cell E (4,3). Then we can regenerate the path from Exit to Start by backtracking.

Alternative State Representation

We have been using a single queue to keep track of the next node to be visited say a (i, j) pair, so far. But this is not the best approach to follow, because it requires a lot of packing and unpacking to and forth the queue. Instead, let’s try another better method which scales really well with higher dimensional data, also possesses less complexity.

An alternative method would be to use separate queues for every dimensions, so in a 3D grid, we would have one queue for each dimension.

As soon as we enqueue some potential information into the queue, x, y and z would go to respective queues. In the same way, dequeue retrieves a triplet of (x,y,z) values at a time.

Pseudo Code to Solve the Dungeon Problem

# Global variables, I intentionally leave the values as ... because # I don't have any meaningful values yet. But it won't affect how
# you understand the problem, I promise.R, C = ...
m = ...
sr, sc = ...
rq, cq = ...# Variables used to keep track of total number of steps to be taken
move_count = 0
nodes_left_in_layer = 0
nodes_in_next_layer = 1# Variable to see whether we already reached at the end or not
reached_end = false# Matrix to keep track of visited cells.
visited = ...# North, South, East and West direction vectors
dr = [-1, +1, 0, 0]
dc = [0, 0, +1, -1]

We start by initializing some global variables. R and C stand for number rows and columns of the dungeon, respectively. The variable m is the input character matrix of size R x C. We store the initial row and column values where we store the starting point of our BFS in variables sr and sc . We use two separate queues rq and cr to store the respective row and column indices of the next node to be visited. Also, we use a couple of variables to keep track of total steps taken to reach the end. nodes_left_in_layer shows the count that how many nodes we have to dequeue before we take a step further and nodes_in_next_layer tracks how many nodes we have added in the BFS expansion, so that we can update nodes_left_in_layer accordingly . The variable reached_end stores whether we already reached the exit cell or not . The variable visited is a matrix of size R x C which is used to mark the cells visited, because we don’t want to visit a same cell again. Variables dr and dc need some explanation, I will cover it soon.

Suppose we are in the red cell (i, j). We have an assumption like a row index can only move between rows and a column index can move between columns. So the only possible row operation is either we can go North by subtracting 1 from i or move South by adding 1 to i . In the same way, we are restricted to move either East or West by adding or subtracting 1 to the column index i.e. j . We use different combinations of direction values to move around the dungeon and that’s why defined it before as variables. I think you got the point.

We’re not done with the problem yet. We just defined a couple of important variables only. The core idea is about to come out.

function solve():
 rq.enqueue(sr)
 cq.enqueue(sc)
 visited[sr][sc] = true

 while rq.size() > 0:
 r = rq.dequeue()
 c = cq.dequeue()
 if m[r][c] == 'E':
 reached_end = true
 break
 explore_neighbors(r, c)
 nodes_left_in_layer --
 if nodes_left_in_layer == 0:
 nodes_left_in_layer = nodes_in_next_layer
 nodes_in_next_layer = 0
 move_count ++
 if reached_end == true:
 return move_count
 return -1function explore_neighbors(r, c):
 for(i=0; i<4: i++):
 rr = r + dr[i]
 cc = c + dc[i]

 if rr < 0 or cc < 0:
 continue
 if rr >= R or cc >= C:
 continue

 if visited[r][c] == true:
 continue
 if m[r][c] == '#':
 continue

 rq.enqueue(rr)
 rc.enqueue(cc)
 visited[r][c] = true

 nodes_in_next_layer ++

Here I have defined two functions namely solve() and explore_neighbors(). We start by enqueuing the initial (i, j) positions from where we start the BFS process and we mark the cell as visited.

Then we do the following steps iteratively until either rq or cq becomes empty.

1. dequeue each element from both rq and cq.
2. we check whether the current position is an exit or not, if yes, we get out of the loop.
3. If the current position isn’t an exit point, then we have to explore its neighbors by invoking the explore_neighbors() function.
4. Inside the explore_neighbors() function, we iteratively find all possible locations and checks for a couple of conditions. I think the conditions are self explanatory.

• The first two conditions check whether we’re out the grid or not. That means, we can’t go beyond the minimum or maximum rows and columns.
• Then we check whether the current location is already been visited before or not. If it’s true, we don’t have to visit it again.
• Also, we have to make sure the current location isn’t blocked, all blocked cells are marked with #.

5. We enqueue the values of current cell and mark it as visited. (Don’t forget, we are inside the explore_neighbors() function call). What happens here is like, we try moving to all possible locations such as north, east, south and west. We then iteratively explore its neighbors. That’s it.

6. Finally we update the value of nodes_in_next_layer and leave .

We’re going back to the solve() function again.

7. We update a couple of parameters to keep track on how many steps we took so far.

8. As soon as we serve an exit point, we go out.

TADAAA!!!

The whole idea and the algorithm are relatively super easy even the pseudo code looks scary.

We started looking at how a maze works and how we can port the same problem into a more scientific one. We saw how we could use grids and adjacency lists to represent the problem. We understood what’s a dungeon problem and how it’s solved using BFS. My idea was to show how we can use BFS to solve a shortest path problem on a grid. That’s pretty much all about it.

In the next post we would have an Introduction to tree algorithms . Until then, bye.