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

Question

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))

```

Answer 1

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':
                destinations.add((r, c))

    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