В таблице представлена информация о времени перелёта (в минутах) на вертолете между населёнными пунктами А, Б, В, Г, Д, Е. Отсутствие числа в таблице означает, что перелёт между…

Короткий ответ: 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 минут. Маршрут: А → В → Е → Г.