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.
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)) \ 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)) # 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")
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).
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
- Item Price Generator Hackerrank Solution
- Insertion Sort Part 2 Hackerrank Solution in C
- Extra Long Factorials Hackerrank Solution
- Java Datatypes Hackerrank Solution
- Smart Number Hackerrank Solution
- Python Average Function Hackerrank Solution
- Company Logo Hackerrank Solution
- Matrix Summation Hackerrank Solution
- A company is repainting its office – HackerRank Solution
- Maximum Product Subarray in O(N) Time – Leetcode Solution
- Minimum number of transformation steps required to make all elements of an array equal
- NxNxN Matrix in Python 3
- Boruvka’s Algorithm in Python
- Roti Prata SPOJ Problem Solution – Complete Solution Approach with C++ and Java Code
- Lee Algorithm in Python | Solution to Maze Routing Problem in Python
- Vending Machine with Python Code
- Top 20 Array Coding Questions for Online Assessment
- Heap Sort Algorithm in Python
- Heap Sort Algorithm|Heap Data Structure
- Insertion Sort Algorithm in Data Structures using Python
- Quick Sort algorithm in data structures and algorithms using Python
- Selection Sort Algorithm In Data Structures and Algorithms using Python
- Searching Algorithms: Linear Search Algorithm
- Bubble Sort Algorithm In Data Structures & Algorithms using Python
- Merge Sort Algorithm in Python
- Binary Search in python
- Linear Search Python
- Sorting Algorithms and Searching Algorithms in Python
- Binary Search In Python
- Adding three matrices