Задать вопрос
@crescent

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

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

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

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

А теперь как такое решить когда источник данных граф и есть начальная точка?
  • Вопрос задан
  • 260 просмотров
Подписаться 1 Простой 4 комментария
Помогут разобраться в теме Все курсы
  • OTUS
    C# Developer. Professional
    6 месяцев
    Далее
  • Ulearn.me
    Основы программирования на примере C#. Часть 1
    1 неделя
    Далее
  • Ulearn.me
    Основы программирования на примере C#. Часть 2
    1 неделя
    Далее
  • Ulearn.me
    Проектирование на языке C#
    1 неделя
    Далее
  • Software-testing.ru
    Программирование на C# для тестировщиков
    10 недель
    Далее
  • Нетология
    Разработчик игр на Unity
    13 месяцев
    Далее
  • OTUS
    C# Developer
    12 месяцев
    Далее
  • XYZ School
    Разработка игр на Unity
    5 месяцев
    Далее
Решения вопроса 2
@mvv-rus
Настоящий админ AD и ненастоящий программист
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных.

Здесь
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Если граф не взвешанный, то запустите обычный bfs, только не кладте в очередь вершины с расчтоянием больше ограничения. Если граф взвешанный, то запустите обычного Дейкстру, только остановитесь, когда зафиксируете вершину с раччтоянием больше допустимого.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@TheDigitalMadness
Программист
Присоединяюсь к написанному выше человеком. Если не взвешенный, то идешь алгоритмом BFS, пока расстояние меньше нужного тебе. Если граф взвешенный, то либо алгоритм Дейкстры, если у вас конкретная точка, либо алгоритм Флойда, если вы не знаете, откуда начинать будете. Затем смотрите просто из необходимой вам точки в списке смежности расстояния
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы