Графы. Как вывести кратчайший путь на Python? (алгоритм уже есть, нужно дополнение)

У меня есть данный код:

from collections import deque

graph = {
    'you': ['alice', 'bob', 'claire'],
    'bob': ['anuj', 'peggy'],
    'alice': ['peggy'],
    'claire': ['thom', 'jonny'],
    'anuj': [],
    'peggy': [],
    'thom': [],
    'jonny': []
}

def person_is_seller(name):
    return name[-1] == 'm'

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + ' is a seller!')
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

search('you')

Да, да, это код из книги "Грокаем алгоритмы". Он берет граф, и строит кратчайший путь от одного человека до другого. В данном случае от "You" до Thom(так как у него имя заканчивается на "m"). Ну как строит... Он лишь проверяет есть ли такой путь. А мне нужно чтобы он именно выводил его, например "You - Claier - Thom". Вот картинка из книги: Граф Еще раз напомню, что это из книги(мало-ли АП):

"Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих | Бхаргава Адитья"

У меня было много идей по этому поводу, но все они громоздкие и занимают немерено времени. Поэтому прошу вас помочь мне. Спасибо всем ответившим!


Ответы (1 шт):

Автор решения: MBo

Заведите ещё один словарь pred, и при переходе из вершины person в вершину b записывайте предка pred[b] = person. В данном, случае, похоже, это все соседи graph[person] здесь search_queue += graph[person]

В конце размотайте цепочку из конечной вершины

→ Ссылка