0

Сейчас читаю книгу "Грокаем алгоритмы". Реализовал поиск в ширину на пайтоне

graph = {}
graph["s"] = {"a","b"}
graph["a"] = {"e"}
graph["b"] = {"a","e"}
graph["e"] = {}

def searchBFS(key, find):
    search_queue = deque()
    search_queue += graph[key]
    searched =[]
    while search_queue:
        obj = search_queue.popleft()
        print("obj:", obj)
        if not obj in searched:
            if obj == find:
                print("Bingo found object")
                return True
            else:
                search_queue += graph[obj]
                searched.append(obj)
    return False

граф представляет собой представленную матрицу смежности по алгоритму Дейкстры из 4 вершин (но не реализация Дейкстры) , в книге пишется, что мол использование "поиска в ширину" даст самый короткий путь от начала до конца, но этого нет, при ряде тестовых запусков количество вершин всегда полное - то есть, все вершины проходятся до конечной искомой точки, и где там "самый короткий путь"? Или ошибка, или я чего-то недогоняю?

1 ответ 1

0

То, что в данном случае выводятся обрабатываемые узлы, не значит, что они участвуют в найденном пути. Если добавить ещё узел

graph["b"] = {"f","a","e"}
graph["e"] = {}
graph["f"] = {"e"}

то он не будет обработан и выведен.

При необходимости вывода кратчайшего пути его нужно регистрировать - например, при добавлении узла в очередь ещё записывать, откуда в него пришли, тогда потом можно размотать цепочку обратно.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.