-2

Есть несколько городов 1,2,3,4,5,6,7,8... но прямого маршрута между каждым нету. Чтоб попасть в 8й с 1го, нужно поехать через 3,5 и 6й. Как найти самый короткий маршрут?

2
  • Ваша попытка решения в студию!
    – user207618
    14 мая 2016 в 8:56
  • я не пробовал ее решить, мне интересен алгоритм
    – emtecif
    14 мая 2016 в 8:57

2 ответа 2

4

Это классическая задача на графах. Она решается при помощи алгоритма Дейкстры.

8
  • зачем сразу Дейкстры, здесь граф не взвешенный, обычного BFS хватит.
    – pavel
    14 мая 2016 в 14:15
  • @pavel - граф взвешенный, все ребра весят 1. BFS найдет все маршруты, затем придется среди них искать оптимальный.
    – gbg
    14 мая 2016 в 14:17
  • не совсем, просто Дейкстры сложность минимум N log N а то и N^2 а лобовой BFS работает за N. И искать не все маршруты, а только 1 самый (он будет оптимальным).
    – pavel
    14 мая 2016 в 14:19
  • @pavel, bfs работает за O(n+m) либо O(n^2) в зависимости от реализации. Дейкстра за O(n^2). За O(n*lb(n)) вроде есть похожий алгоритм, но это не совсем дейкстра.
    – Qwertiy
    14 мая 2016 в 19:51
  • @gbg, bfs как раз ищет оптимальный.
    – Qwertiy
    14 мая 2016 в 19:51
0

Задача может решаться с помощью алгоритма А*

Ваш ответ

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

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