Graph Theory | BFS Shortest Path Problem on a Grid

栏目: IT技术 · 发布时间: 3年前

内容简介:Hi all, welcome back to another post of my brand new series on Graph Theory namedI hope you have an idea about what isMany problems in Graph Theory could be represented using grids, because interestingly grids are a form of

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.

Photo by Author

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.

Photo by Author

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.
Photo bu Author

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.

Photo by Author

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.

Photo by Author

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.

Photo by Author

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.

Photo by Author

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.


以上所述就是小编给大家介绍的《Graph Theory | BFS Shortest Path Problem on a Grid》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

浅薄

浅薄

[美]尼古拉斯·卡尔 / 刘纯毅 / 中信出版社 / 2015-11 / 49.00 元

互联网时代的飞速发展带来了各行各业效率的提升和生活的便利,但卡尔指出,当我们每天在翻看手机上的社交平台,阅读那些看似有趣和有深度的文章时,在我们尽情享受互联网慷慨施舍的过程中,我们正在渐渐丧失深度阅读和深度思考的能力。 互联网鼓励我们蜻蜓点水般地从多种信息来源中广泛采集碎片化的信息,其伦理规范就是工业主义,这是一套速度至上、效率至上的伦理,也是一套产量最优化、消费最优化的伦理——如此说来,互......一起来看看 《浅薄》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

MD5 加密
MD5 加密

MD5 加密工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具