В таблице представлена информация о времени перелёта (в минутах) на вертолете между населёнными пунктами А, Б, В, Г, Д, Е. Отсутствие числа в таблице означает, что перелёт между этими пунктами напрямую не осуществляется. А Б В Г Д Е А 3 3 7 Б 3 5 6 В 3 5 12 2 Г 12 5 2 Д 7 5 Е 6 2 2 Определите самый быстрый маршрут из населённого пункта А в населённый пункт Г. Ответ в мин

Короткий ответ: fastest путь А → В → Е → Г, общее время 7 минут. Подробное решение (по шагам) 1) Построим ориентированный граф из таблицы - А → Б = 3 - А → В = 3 - А → Е = 7 - Б → А = 3 - Б → В = 5 - Б → Е = 6 - В → А = 3 - В → Б = 5 - В → Д = 12 - В → Е = 2 - Г → В = 12 - Г → Д = 5 - Г → Е = 2 - Д → А = 7 - Д → Г = 5 - Е → Б = 6 - Е → В = 2 - Е → Г = 2 2) Применим алгоритм Дейкстры для поиска кратчайшего пути из А в Г Инициализация: - d(A) = 0, pred(A) = null - все прочие d = ∞ После первых обновлений из A: - d(B) = 3, pred(B) = A - d(В) = 3, pred(В) = A - d(E) = 7, pred(E) = A Выбираем узел с минимальным d: B (3) или В (3). Возьмём B. Из B обновления: - через B к А: 3 + 3 = 6 (лучше 0? нет) - к В: 3 + 5 = 8 (лучше 3? нет) - к Е: 3 + 6 = 9 (лучше 7? нет) Теперь незvisited узлы: В (3), E (7), D и Г бесконечны. Выбираем узел В (3). Из В обновления: - к А: 3 + 3 = 6 (нет) - к Е: 3 + 2 = 5 (улучшает E: d(E) = 5, pred(E) = В) - к Д: 3 + 12 = 15 (d(D) = 15) Теперь имеем: d(E) = 5, pred(E) = В; d(G) = ∞; d(D) = 15. Выбираем E (d = 5). Из E обновления: - к Г: 5 + 2 = 7 (d(G) = 7, pred(G) = Е) - к Б: 5 + 6 = 11 (нет) - к В: 5 + 2 = 7 (нет) Теперь следующего узла с меньшим d: Г (7) — это цель. Можно остановиться и зафиксировать кратчайшее расстояние. 3) Восстановление пути - pred(G) = Е, pred(Е) = В, pred(В) = А. - Значит маршрут: А → В → Е → Г. - Стоимость: А→В = 3, В→Е = 2, Е→Г = 2 → всего 7 минут. Ответ: 7 минут. Маршрут: А → В → Е → Г.