Optimal Path with BFS

Uninformed Path Search

This blog is about finding an Optimal path from source to target using BFS. The path also has obstacles in it. I am using BFS as it is an uninformed search. If we have more information about the source target, path & distance, we can use an informed search (A* search). The description of the problem statement is as below :
You have given an MxN matrix where M is the number of rows and N is the number of columns. The user will fill the matrix with either of these — [S, T, ., #] where S is the source, T is the target, # is the obstacles, and ‘.’ is the space we can move.

In the above image, you can see we can move diagonally, upward, down, top, bottom but only one step at a time. There can be more than one path, but we need to find the optimal path. I am explaining the step-by-step solution to solve this problem, and I will also attach the whole code written in python.

Our algorithm should return path 1 because it is optimal.

Here is the algorithm :

Step 1: Take input from the user for the number of rows and columns.

Step 2: Take input of the whole matrix from user row-wise

Step 3: Find the source and target location.

Step 4: Pass the source and target location in BFS Procedure along with matrix.

Step 5: BFS Procedure will return the optimal path if there is any between source and destination and if not it will return -1.

Now the central part is how the BFS Procedure/Method/Function works :

It starts with tagging all positions in the matrix as “not visited” except the position of source & destination; Post that, it adds the source location to the empty queue and starts a loop until the queue is empty or you find the optimal path for the target location.

In the loop, it deque the queue element and finds corresponding moveable positions in the matrix from the element’s position that has been dequeue.

So now the question is how to find the all moveable position from a particular position in the matrix. Let’s find out together, and the logic of finding all possible positions from any position is the heart of the program.

As we can move in any direction so maximum valid direction to move will be eight

rowNum = [-1, 0, 1, -1, -1, 1, 0, 1]

colNum = [0, -1, 1, -1, 1, -1, 1, 0]

you can loop through the current position of your element with rownum and colNum and check if it is valid position (rowPos >= 0 && rowPos < M ), (colNum >= 0 && colNum < =N)

After finding all the valid positions of an element, We check if there is an obstacle present in that location. If there is no obstacle we mark the node visited and check whether we reached our target or not. If not we add that position without obstacle to the queue to move further.

Post this loop we get the optimal path if there is any!

I know it’s a little hard to understand attaching a link to the code I have done. I modified the code present in GeeksOfGeeks, so full credit and tons of thank you to them.