如何使用bfs在未加权图上实现多源最短路径？

Question

我有这样的网格

000000000
0AAA00000
0AA000000
0AAA00000
000000000
000000000
000000B00
00000BBB0
00000BBBB

现在如何使用bfs找到从A到B的最短路径？A和A之间的旅行费用为0,A-0或0-B或0-0为1.我已经尝试在每个A上单独应用bfs并采用最小值.但这似乎不起作用.还有其他办法吗？

Answer 1

多源BFS 的工作方式与常规 BFS 完全相同，但不是从单个节点开始，而是在开始时将所有源 ( A's) 放入队列中。也就是说，遍历网格以找到所有A's 并使用距离为 0 的所有这些初始化您的 BFS 队列。然后像往常一样继续 BFS。

下面是一个 Python 实现示例：

from collections import deque
from itertools import product

def get_distance():
    grid = [['0', '0', '0', '0', '0', '0', '0', '0', '0'],
            ['0', 'A', 'A', 'A', '0', '0', '0', '0', '0'],
            ['0', 'A', 'A', '0', '0', '0', '0', '0', '0'],
            ['0', 'A', 'A', 'A', '0', '0', '0', '0', '0'],
            ['0', '0', '0', '0', '0', '0', '0', '0', '0'],
            ['0', '0', '0', '0', '0', '0', '0', '0', '0'],
            ['0', '0', '0', '0', '0', '0', 'B', '0', '0'],
            ['0', '0', '0', '0', '0', 'B', 'B', 'B', '0'],
            ['0', '0', '0', '0', '0', 'B', 'B', 'B', 'B']]
    R = C = 9  # dimensions of the grid
    queue = deque()
    visited = [[False]*C for _ in range(R)]
    distance = [[None]*C for _ in range(R)]
    for row, col in product(range(R), range(C)):
        if grid[row][col] == 'A':
            queue.append((row, col))
            distance[row][col] = 0
            visited[row][col] = True
    while queue:
        r, c = queue.popleft()
        for row, col in ((r-1, c), (r, c+1), (r+1, c), (r, c-1)):  # all directions
            if 0 <= row < R and 0 <= col < C and not visited[row][col]:
                distance[row][col] = distance[r][c] + 1
                if grid[row][col] == 'B':
                    return distance[row][col]
                visited[row][col] = True
                queue.append((row, col))    

print(get_distance())  # 6

Answer 2

BFS会好的.首先,按网格中A的所有位置初始化队列.每次,你在队列的前面弹出一个位置,同时推动所有可以通过1步到达并且尚未被访问过的位置.第一次访问B时,您将获得从A到B的最短路径.