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

Question

I have a grid like this:

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

现在我如何使用BFS找到从A到B的最短路径？A和A之间旅行的费用为0，A-0或0-B或0-0的费用为1。 我尝试对每个A分别应用BFS，并取其中的最小值。但是那似乎行不通。还有其他方法吗？

- Tamim Addari

---

你可以从任何一个 A 开始，是吗？ - sve

你目前做了什么？ - rendon

尝试使用Dijkstra算法从每个'A'开始。如果您在实现算法时遇到问题，请回来。 - rendon

有没有使用BFS的方法来实现这个？ - Tamim Addari

是的，只需最初将所有起始节点排队即可。 - BlueRaja - Danny Pflughoeft

Answer 1

一种多源 BFS 与普通的 BFS 完全相同，但是不同的是你需要将所有源节点（A）在开始时都放入队列中。也就是说，先扫描整个网格以找到所有的 A，然后将它们全部以距离 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

- Eugene Yarmash

Answer 2

BFS算法是可行的。首先，你需要初始化一个队列，将A所有格子的位置放入队列中。每一次操作，你要弹出队列头上的位置，并将其可以到达的、且未访问过的位置全部加入队列中。当你第一次访问到B时，就可以得到从A到B的最短路径。

- notbad