Shortest path from source to destination in matrix – Code

Shortest path in matrix is to find the shortest distance from the the source to the destination. As you know, graph can be represented as adjacent matrix. Therefore, we can use the Breadth First Search algorithm in graph to solve this problem.

BFS starts from the source node. It explores all its adjacent nodes before going to the next level adjacent nodes. It is usually implemented with Queue. You visit each node in the queue until you find the destination. This question allows you to move in 4 directions, i.e, left, right, up and down. So, when visiting each node in queue, your next move is to visit cell’s 4 neighbors.

The trick about this question is that you are no only required to return shortest distance. You are also required to print the shortest path. The solution is to save the previous visited nodes in the cell object. At the end, you use linked list to track all nodes from destination to the source.

Facebook Interview Question (CareerCup):
Given a MxN matrix where each element can either be 0 or 1. We need to print the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.
public void print(int[][] matrix, int[] start, int[] end){
}

Java Code:

Output:
[(2,4), (3,4), (3,3), (3,2)]

O Notation:
Time complexity: O(n^2)
Space complexity: O(n^2)

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!

Action Items:
Download ShortestPathBetweenCells.zip
Shortest path between cells in matrix tutorial
The complete list of coding interview questions

Comments are closed