CODEWITHSUNDEEP
pythongraphshortest-pathbreadth-first-search
elixir
elixir

Reputation: 1442

Shortest path in a grid using BFS

The grid consists of following items as python list of lists

g = [
    ['1', '1', '1', '1', '1'],
    ['S', '1', 'X', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['X', '1', '1', 'E', '1'],
    ['1', '1', '1', '1', 'X']
]

S indicates the start, E indicates the end.

1 indicates the allowed paths, X are not allowed paths

A simple BFS traversal code is 

def find_path_bfs(s, e, grid):
    queue = list()
    path = list()
    queue.append(s)

    while len(queue) > 0:
        node = queue.pop(0)
        path.append(node)
        mark_visited(node, v)

        if node == e:
            break

        adj_nodes = get_neighbors(node, grid)
        for item in adj_nodes:
            if is_visited(item, v) is False:
                queue.append(item)

    return path

The algorithm, as far as I can tell is traversing correctly with the following output 

[(1, 0), (1, 1), (2, 0), (0, 0), (2, 1), (0, 1), (2, 1), (0, 1), (2, 2), (3, 1), (0, 2), (2, 2), (3, 1), (0, 2), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 4), (3, 3)]

Each tuple in the list represents the indices for the node in the original graph.

How can rewrite my BFS code to return the shortest path instead of the entire traversal path followed to reach the destination node? I have spent hours to find answers on my own but so far I have been unsuccessful.

Upvotes: 2

Views: 9887

Answers (1)

ingvar
ingvar

Reputation: 4377

In order to get shortest path you should save path to current node in your queue too, so format of queue item will be:

(node, path_to_this_node)

Modified code:

def find_path_bfs(s, e, grid):
    queue = [(s, [])]  # start point, empty path

    while len(queue) > 0:
        node, path = queue.pop(0)
        path.append(node)
        mark_visited(node, v)

        if node == e:
            return path

        adj_nodes = get_neighbors(node, grid)
        for item in adj_nodes:
            if not is_visited(item, v):
                queue.append((item, path[:]))

    return None  # no path found

Upvotes: 5

Related Questions