Lee Algorithm In Python | Solution To Maze Routing Problem In Python

Introduction

Definition: The Lee algorithm is one feasible solution for maze routing problems based on a breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory. We will learn Lee Algorithm in Python by Solution to Maze Routing Problem.

The Lee algorithm has the properties of
a) always finding a path if one exists and
b) always finding the path with the lowest feasible cost.

In this article, only algorithms with these qualities will be addressed. Lee’s algorithm and its variants require the least amount of storage of any known algorithm. There is no cost matrix, nor are there any successor tables.

Lee Algorithm

Step 1 – Make an empty queue and enqueue the source cell with a distance of 0 from the source (itself), marking it as visited.
Step 2 – Loop until the queue is empty.

Dequeue the front node.
If the popped node is the destination node, then return its distance.
Otherwise, for each of four adjacent cells of the current cell, enqueue each valid cell with +1 distance and mark them as visited.

Step 3 – Return false if the destination is not reached after processing all queue nodes.

Click here to read more about the Lee algorithm on Wikipedia.

Maze Routing Problem with Lee Algorithm

In this problem, we will apply the Lee Algorithm, which is based on the breadth-first-search (BFS) procedure. In this case, we use a queue and a matrix to determine which cell has been visited, and we continue this procedure until we discover the shortest path from the source cell to the destination cell.

We are given a maze in the form of a binary rectangular matrix in this problem, and our objective is to identify the shortest path between a particular source cell and a destination cell. The maze is represented as an MxN matrix, with each element having a value of 0 or 1. A route may only be formed from a cell if its value is 1. We can only move one step in one of the four directions at a time.

Consequently, the following are appropriate steps:

Shift Up: (a, b) ——> (a – 1, b)
ShiftLeft: (a, b) ——> (a, b – 1)
Shift Down: (a, b) ——> (a + 1, b)
Shift Right: (a, b) ——> (a, b + 1)

Consider this example

Take the binary matrix shown below as an example. The shortest path from source to destination has a length of 5 if source and destination are (0, 0) and (3, 2), respectively.

[ 1  1  1  1  1  0  0 ]
[ 1  1  1  1  1  1  0 ]
[ 1  0  1  0  1  1  1 ]
[ 1  1  1  1  1  0  1 ]
[ 0  0  0  1  0  0  0 ]
[ 1  0  1  1  1  0  0 ]
[ 0  0  0  0  1  0  0 ]

Solving Maze Routing Problem with Lee Algorithm in Python

#importing libraries
import sys
from collections import deque

# All four potential movements from a cell are listed here.
row = [-1, 0, 0, 1]
col = [0, -1, 1, 0]

# Whether it is possible to move from the current position to position (row, col)
#  is determined by this function. If row, col is not in a legal location, 
# has a value of 0, or has already been visited, the method returns false.

def Validate(matrix, visited, row, col):
	return (row >= 0) and (row < len(matrix)) and (col >= 0) and (col < len(matrix[0])) \
		   and matrix[row][col] == 1 and not visited[row][col]


# Find the shortest path between sources and destinations in a matrix.
def Shortest_Path(matrix, source, destination):

	# get source cell (i, j)
	i, j = source
	
	# get destination cell (x, y)
	x, y = destination

	# base case: invalid input
	if not matrix or len(matrix) == 0 or matrix[i][j] == 0 or matrix[x][y] == 0:
		return -1

	# `M × N` matrix
	(M, N) = (len(matrix), len(matrix[0]))
	
	# construct a matrix to keep track of visited cells
	visited = [[False for x in range(N)] for y in range(M)]
	
	# create an empty queue
	q = deque()
	
	# mark the source cell as visited and enqueue the source node
	visited[i][j] = True

	# (i, j, dist) represents matrix cell coordinates, and their
	# minimum distance from the source
	q.append((i, j, 0))

	# stores length of the longest path from source to destination
	min_dist = sys.maxsize

	# loop till queue is empty
	while q:
		# dequeue front node and process it
		(i, j, dist) = q.popleft()

		# (i, j) represents a current cell, and `dist` stores its
		# minimum distance from the source.
		# if the destination is found, update `min_dist` and stop
		if i == x and j == y:
			min_dist = dist
			break

		# check for all four possible movements from the current cell
		# and enqueue each valid movement
		for k in range(4):
		    
			# check if it is possible to go to position
			# (i + row[k], j + col[k]) from current position
			if Validate(matrix, visited, i + row[k], j + col[k]):
			    
				# mark next cell as visited and enqueue it
				visited[i + row[k]][j + col[k]] = True
				q.append((i + row[k], j + col[k], dist + 1))

	if min_dist != sys.maxsize:
		return min_dist
	else:
		return -1


if __name__ == '__main__':

	matrix = [
		[1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
		[0, 1, 1, 1, 1, 1, 0, 1, 0, 1],
		[0, 0, 1, 0, 1, 1, 1, 0, 0, 1],
		[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
		[0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
		[1, 0, 1, 1, 1, 0, 0, 1, 1, 0],
		[0, 0, 0, 0, 1, 0, 0, 1, 0, 1],
		[0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
		[1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
		[0, 0, 1, 0, 0, 1, 1, 0, 0, 1]
	]

	source = (0, 0)
	destination = (3, 2)

	min_dist = Shortest_Path(matrix, source, destination)

	if min_dist != -1:
		print("The length of the shortest route between sources and destinations :- ", min_dist)
	else:
		print("The source cannot lead to the destination")

Output:

Explanation:

The above-mentioned solution iteratively travels through each matrix cell in a BFS fashion until it reaches our destination cell or runs out of paths. The complexity of the entire procedure is O(MxN), where M and N are the dimensions of the matrix. Additionally, the space complexity is O since we need a separate MxN matrix to hold the visited state of cells (MxN).

We have now learned how to use the Lee Algorithm in Python to determine the shortest path across a maze between any two places. Solution iteratively travels through each matrix cell in a BFS fashion until it reaches our destination cell or runs out of paths. The complexity of the entire procedure is O(MxN), where M and N are the dimensions of the matrix. Additionally, the space complexity is O since we need a separate MxN matrix to hold the visited state of cells (MxN).

FAQs

What is Maze Routing Problem?

The maze routing problem is nothing but a problem that needs to be solved by any method and Lee Algorithm is considered the best algorithm to solve this problem.

What is Lee Algorithm?

The Lee algorithm is one feasible solution for maze routing problems based on a breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory – Wikipedia

Also Read:

Lee Algorithm in Python | Solution to Maze Routing Problem in Python