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"}

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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