使用BFS的网格中的最短路径 [英] Shortest path in a grid using BFS

问题描述

网格由以下各项组成，如列表的python列表

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表示开始，E表示结束.

S indicates the start, E indicates the end.

1表示允许的路径，X表示不允许的路径

1 indicates the allowed paths, X are not allowed paths

一个简单的BFS遍历代码是

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.

如何重写我的BFS代码以返回最短路径，而不是返回到达目标节点的整个遍历路径?不成功.

推荐答案

为了获得最短路径，您也应该将当前节点的路径也保存在队列中，因此队列项的格式为:

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)

修改后的代码:

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

这篇关于使用BFS的网格中的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！