2

Как реализовать поиск кратчайшего пути из точки A в B, проходящего через точку С в невзвешенном графе.

Можно ли для такого использовать волновой алгоритм? И как его потребуется изменить?

1 ответ 1

3

С помощью поиска в ширину (BFS) будем находить кратчайшее расстояние между двумя вершинами.

Тогда решение вашей задачи сводится к поиску кратчайшего расстояния между вершинами A и С, и нахождением кратчайшего расстояния от C к B. Т.е. надо будет запустить BFS два раза, от вершины А и от вершины C.

1
  • Благодарю.
    – Flasko
    22 ноя 2013 в 1:39

Ваш ответ

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

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