Как найти кратчайший путь в графе поиском в ширину?

Question

[Максим Золотой]

В описании алгоритма Поиск в ширину написано "так вы найдете кратчайший путь к заданной точке"
Но по факту я просто узнаю есть ли заданный узел в графе или нет.
А как мне узнать путь то? (список узлов через которые идет путь)

Answer 1

[Rsa97]

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

Comments

[Максим Золотой]

Но там же получится будут данные и о тех узлах которые проверяли, но маршрут через них не пошел

[Rsa97]

Максим Золотой, Узел добавляется в очередь один раз, в нём не может быть информации о нескольких предыдущих узлах, только об одном.