Поиск куда можно добраться по графу за время?

Question

[crescent]

По графу в основном ищется кратчайший путь.

А есть алгоритм по поиску куда можно добраться за определленое время/вес/ресурс.

Те если человек в поле то за час он может находиться в окружности радиуса 5км

А теперь как такое решить когда источник данных граф и есть начальная точка?

Comments

[SunTechnik]

Так вроде понятно:
Рекусивный обход от начальной точки.
Доступные точки окрашиваем (ставим признак)
Из доступного времени новой точки вычитаем вес ребра, по которому попали в точку. Точки, которые уже окрашены - для них поиск не запускается..

[Akina]

Здесь подойдёт волновой алгоритм либо поиск в ширину. С прерыванием ветви поиска по превышению заданного лимита.

[Alexandroppolus]

Akina, если все ребра одинаковы, то да, это оптимальный вариант. Иначе - Дейкстра или даже лучше UCS ("поиск по критерию стоимости")

[Akina]

Alexandroppolus, так UCS - это тот же поиск в ширину, только для случая различных весов рёбер. А Дейкстра тут скорее всего не будет оптимален просто потому, что по классике он посещает все вершины, а для поставленной задачи это в общем случае очевидно избыточно.

Answer 1

[MVV]

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных.

Здесь

Answer 2

[Wataru]

Если граф не взвешанный, то запустите обычный bfs, только не кладте в очередь вершины с расчтоянием больше ограничения. Если граф взвешанный, то запустите обычного Дейкстру, только остановитесь, когда зафиксируете вершину с раччтоянием больше допустимого.

Answer 3

[Захар Буров]

Присоединяюсь к написанному выше человеком. Если не взвешенный, то идешь алгоритмом BFS, пока расстояние меньше нужного тебе. Если граф взвешенный, то либо алгоритм Дейкстры, если у вас конкретная точка, либо алгоритм Флойда, если вы не знаете, откуда начинать будете. Затем смотрите просто из необходимой вам точки в списке смежности расстояния