# Shortest possible path between closest pair of specific nodes in a maze

Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $$O(MN)$$ time? (M rows, N cols). $$O(RMN)$$ time would also be sufficient (R is numbers of 'r' nodes).

Below is an adopted version the Lee algorithm from here that uses BFS to find the shortest distance between a given a single source node and a single destination node in $$O(MN)$$ time.

Can I extend this framework for the problem at hand? Any ideas are much appreciated.

import sys
from collections import deque

# Below lists detail all four possible movements from a cell
row = [-1, 0, 0, 1]
col = [0, -1, 1, 0]

# Function to check if it is possible to go to position (row, col)
# from the current position. The function returns false if row, col
# is not a valid position or has a value 0 or already visited.
def isValid(mat, visited, row, col):
return (row >= 0) and (row < len(mat)) and (col >= 0) and (col < len(mat[0])) \
and mat[row][col] == '.' or mat[row][col] == 'r' or mat[row][col] == 'b' and not visited[row][col]

# Find the shortest possible route in a matrix mat from source src to
# destination dest
def findShortestPathLength(mat):
src = (1, 1)
(M, N) = (len(mat), len(mat[0]))
dest = (M-2, N-2)
# get source cell (i, j)
i, j = src

# get destination cell (x, y)
x, y = dest

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

# 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 isValid(mat, 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 sys.maxsize

mat = [
['o','o','o','o','o','o'],
['o','r','.','.','b','o'],
['o','r','.','.','b','o'],
['o','r','.','.','b','o'],
['o','o','o','o','o','o'],
]

print(findShortestPathLength(mat))

mat = [
['o','o','o','o','o'],
['o','r','o','o','o'],
['o','o','o','o','o'],
['o','o','o','b','o'],
['o','o','o','o','o'],
]

print(findShortestPathLength(mat))

mat = [
['o','o','o','o','o','o','o','o'],
['o','.','.','r','.','.','.','o'],
['o','o','o','o','o','o','.','o'],
['o','.','.','.','.','.','.','o'],
['o','.','o','o','o','o','o','o'],
['o','.','.','b','.','.','.','o'],
['o','o','o','o','o','o','o','o'],
]

print(findShortestPathLength(mat))

$$$$

• Hmm, I have been using this "Lee algorithm" for tens of times, if not hundreds of times. This is the first time I have heard of that name. Dec 3 '21 at 8:38
• @JohnL. Same here. This "Lee algorithm" is a flood fill with a very thin disguise. Dec 4 '21 at 11:09

You can append all 'r' nodes to the initial empty queue.

Instead of checking whether the front node is the single destination node, check whether the front node is in the set of all destination nodes.

With the two extensions above, the Lee algorithm will be able to find the shortest distance between the closest pair of 'r' and 'b' nodes in $$O(MN)$$ time.

Here is an implementation in Python. Instead of checking the front node, i.e., when the node is popped out of the queue, this implementation check each node when it was pushed into the queue. This minor change improves the performance slightly.

from collections import deque

def find_shortest_path_length(mat):
"""Return the length of the shortest route from an 'r' node to a 'b' node

mat is a 2-dimensional list of nodes. There are four kinds of node. An 'r'
node is a source node. A 'b' node is a destination node. A '.' node can
be passed while a 'o' node is an obstructed node that cannot be passed.
"""
m, n = len(mat), len(mat[0])
visited = [[False] * n for row in range(m)]
q = deque()
destinations = set()

def should_visit(row, col):
"""Return true if (row,col) is a valid position not processed yet"""
return 0 <= row < m and 0 <= col < n and \
mat[row][col] != 'o' and not visited[row][col]

for r in range(m):
for c in range(n):
if mat[r][c] == 'r':
q.append((r, c))
visited[r][c] = True
elif mat[r][c] == 'b':

dist = 1  # the level in breadth-first-search.
while q:
for _ in range(len(q)):
(r, c) = q.popleft()

for (new_r, new_c) in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if should_visit(new_r, new_c):
if (new_r, new_c) in destinations:
return dist
q.append((new_r, new_c))
visited[new_r][new_c] = True
dist += 1

# The destinations can not be reached.
return -1

• Can you elaborate what you mean by front node? Also, in order to append all 'r' nodes to the initial empty queue, I would need to know their position in the maze. How would I obtain their positions? Thanks Dec 3 '21 at 8:57
• "front node" as in this line of comment of your code, "dequeue front node and process it". Dec 3 '21 at 9:16
• Loop through all nodes, adding each node to the initial queue whenever the node is an 'r' node. Also add each node to the set of all destination nodes whenever the node is a 'b'` node. Dec 3 '21 at 9:17