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.

shortest path in matrix bfs

Facebook Interview Question:
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){




case 1: there is no path. case 2: [(0,2), (1,2), (1,1)]

O Notation:
Time complexity: O(mxn)
Space complexity: O(mxn)
m is number of rows, n is number of columns

Download ShortestPathBetweenCellsBFS.js
Shortest path between cells in matrix (YouTube)
Java Coding Interview Pocket Book (2nd Edition)

Comments are closed