Графы. Как вывести кратчайший путь на 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 шт):
Заведите ещё один словарь pred, и при переходе из вершины person в вершину b записывайте предка pred[b] = person. В данном, случае, похоже, это все соседи graph[person] здесь search_queue += graph[person]
В конце размотайте цепочку из конечной вершины