CODEWITHSUNDEEP
algorithmshortest-pathbreadth-first-search
Tamim Addari
Tamim Addari

Reputation: 7841

How to implement a multi-source shortest path on unweighted graph using BFS?

I have a grid like this:

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

Now how do I find the shortest path from A to B using BFS? the cost of traveling between A and A is 0 and A-0 or 0-B or 0-0 is one. I have tried applying BFS on each of the A individually and taken the minimum of that. But that doesn't seems to work. Is there any other approach?

Upvotes: 4

Views: 10548

Answers (2)

Eugene Yarmash
Eugene Yarmash

Reputation: 149853

A multiple-source BFS works in exactly the same way as regular BFS, but instead of starting with a single node, you would put all your sources (A's) in the queue at the beginning. That is, make a pass over the grid to find all A's and initialize your BFS queue with all of them at distance 0. Then proceed with BFS as normal.

Here's an example Python implementation:

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

Upvotes: 15

notbad
notbad

Reputation: 2887

BFS will be okay. First you init the queue by all the positions of A in the grid. And each time, you pop a position at the front of the queue ,at the same time, push all the positions which can be reached by 1 step and hasn't been visited yet. The first time you visit a B, you get the shortest path from A to B.

Upvotes: 11

Related Questions