Некоторая авиакомпания предоставляет следующие перелетные маршруты: Из Москвы в Сочи за 8 часов, в Питер за 2 часа, в Казань за 20 часов Из Питера в Ростов за 15 часов Из Сочи в…
Некоторая авиакомпания предоставляет следующие перелетные маршруты: Из Москвы в Сочи за 8 часов, в Питер за 2 часа, в Казань за 20 часов Из Питера в Ростов за 15 часов Из Сочи в Питер за 5 часов, в Ростов за 5 часов Из Ростова в Москву за 8 часов, в Волгоград за 7 часов, в Мурманск за 3 часа Из Казани в Ростов за 1 час Из Мурманска в Волгоград за 2 часа Из Волгограда в Саранск за 4 часа, во Владивосток за 10 часов, в Мытищи за 12 часов, в Казань за 1 час Из Саранска в Владивосток за 3 часа Из Владивостока в Мытищи за 2 часа Из Мытищ в Москву за 1 час. За какое наименьшее время путешественник может добраться из Москвы в Мытищи следуя только этими маршрутами?
Кратко: минимальное время — 27 часов. Маршрут: Москва → Сочи → Ростов → Мурманск → Волгоград → Саранск → Владивосток → Мытищи.
Пошаговое решение (пояснение по сути задачи как графа и поиска кратчайшего пути)
- Запишем маршруты как ориентированный граф с весами (время в часах):
- Москва → Сочи: 8
- Москва → Петербург: 2
- Москва → Казань: 20
- Петербург → Ростов: 15
- Сочи → Петербург: 5
- Сочи → Ростов: 5
- Ростов → Москва: 8
- Ростов → Волгоград: 7
- Ростов → Мурманск: 3
- Казань → Ростов: 1
- Мурманск → Волгоград: 2
- Волгоград → Саранск: 4
- Волгоград → Владивосток: 10
- Волгоград → Мытищи: 12
- Саранск → Владивосток: 3
- Владивосток → Мытищи: 2
- Мытищи → Москва: 1
- Применим алгоритм Дейкестры для поиска кратчайшего пути из Москвы к Мытищам.
- Старт: Москва (0). Возможные соседи: Сочи (8), Петербург (2), Казань (20). Дистанции: Sochi 8, Piter 2, Kazan 20.
- Выбираем минимальную незавершённую вершину: Петербург (2). Из Петербурга: Ростов за 15. Новая дистанция до Ростова: 2 + 15 = 17.
- Далее выбираем минимальную: Сочи (8). Из Сочи: Петербург через Сочи снова, но 8+5 = 13 до Петербурга (лучше не стало); Ростов 8+5 = 13 (обновляем Ростов до 13).
- Выбираем Ростов (13). Из Ростова: Москва (8), Волгоград (7), Мурманск (3). Новые дистанции: Москва 21 (не лучше 0), Волгоград 13+7 = 20, Мурманск 13+3 = 16.
- Выбираем Мурманск (16). Из Мурманска: Волгоград 2 → новая дистанция до Волгограда: 16+2 = 18 (лучше 20).
- Выбираем Волгоград (18). Из Волгограда: Саранск 4 → 22, Владивосток 10 → 28, Мытищи 12 → 30.
- Выбираем Саранск (22). Из Саранска: Владивосток 3 → новая дистанция до Владивостока: 25 (улучшение с 28).
- Выбираем Владивосток (25). Из Владивостока: Мытищи 2 → новая дистанция до Мытищ: 25+2 = 27 (улучшение с 30).
- Выбираем Мытищи (27). Это целевая вершина, кратчайшее расстояние найдено: 27 часов.
- Восстановим путь (через предшественников):
- Мытищи получило расстояние 27 от Владивостока.
- Владивосток получал предшественник: Саранск.
- Саранск получал предшественник: Волгоград.
- Волгоград получал предшественник: Мурманск.
- Мурманск получал предшественник: Ростов.
- Ростов получал предшественник: Сочи.
- Сочи получал предшественник: Москва.
Итак, кратчайший путь: Москва → Сочи → Ростов → Мурманск → Волгоград → Саранск → Владивосток → Мытищи, суммарно 8 + 5 + 3 + 2 + 4 + 3 + 2 = 27 часов.
Ответ: наименьшее время путешествия из Москвы в Мытищи — 27 часов.
