Блог

Сетка состоит из следующих элементов в виде списка списков python

 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 указывает на конец.

1 указывает разрешенные пути, X — недопустимые пути

Простой код обхода BFS является

 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
  

Алгоритм, насколько я могу судить, проходит правильно со следующим выводом

 [(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)]
  

Каждый кортеж в списке представляет индексы для узла в исходном графике.

Как можно переписать мой код BFS, чтобы вернуть кратчайший путь вместо всего пройденного пути для достижения конечного узла?Я потратил часы, чтобы найти ответы самостоятельно, но пока мне это не удалось.

Чтобы получить кратчайший путь, вы также должны сохранить путь к текущему узлу в своей очереди, поэтому формат элемента очереди будет:

 (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