Поиск вектора пути в графе, имеется обход в графа в ширину(с использованием стека)?

Question

[Antonzm]

1.Есть обход в ширину(не рекурсивный!)(начинает с начальной вершины , заканчивается когда достигнута нужная вершина).
2.Есть стек , и хранилище , в котором лежат все вершины в порядке их добавления в стек.
Как реализовать поиск именно вектора пути ?

Comments

[uvelichitel]

Путей много может быть если граф не деревянный...

[Antonzm]

uvelichitel: ну я имею ввиду поиск оптимального пути из А в Б

Answer 1

[uvelichitel]

В комментариях вы уточнили, что интересует оптимальный путь. Оптимальный путь обходом в ширину это алгоритм Дейкстры. Вкратце, в стек(вектор пути) в позицию каждой вершины записывается имя последней предыдущей на кратчайшем пути. Подробно описано например здесь https://habrahabr.ru/post/111361/