В таблице представлена информация о расстоянии проезда (в километрах) между городами А, Б, В, Г, Д, Е. Отсутствие числа в таблице означает, что дороги между двумя городами нет. А…
В таблице представлена информация о расстоянии проезда (в километрах) между городами А, Б, В, Г, Д, Е. Отсутствие числа в таблице означает, что дороги между двумя городами нет. А Б В Г Д Е А 6 10 5 12 Б 6 10 В 10 10 2 7 Г 5 2 9 Д 12 8 Е 7 9 8 Маша живет в городе А. Пользуясь таблицей, определите кратчайший путь, который преодолеет Маша, двигаясь в город Е. Передвигаться можно только по дорогам. Ответ в км
Понял задачу. Переведём таблицу в граф: каждая пара городов соединена дорогой с указанной длиной, отсутствие числа означает нет дороги. Узлы: А, Б, В, Г, Д, Е. Рёбра (дороги) и веса:
- А–Б = 6
- А–В = 10
- А–Г = 5
- А–Д = 12
- Б–В = 10
- В–Г = 2
- В–Е = 7
- Г–Е = 9
- Д–Е = 8
Задача: найти кратчайший путь из А в Е.
Метод: алгоритм Дейкстры.
Пошагово:
- Начальные расстояния: d(А)=0, все остальные бесконечны.
- После обработки А обновляем соседей: d(Б)=6, d(В)=10, d(Г)=5, d(Д)=12, d(Е)=∞.
- Выбираем ближайшую не посещённую вершину: Г (5). Из Г обновляем: d(В) = min(10, 5+2) = 7 d(Е) = min(∞, 5+9) = 14
- Выбираем следующую ближайшую: Б (6). Обновления: далее дорога через Б к Е отсутствует, каналы через Б не улучшают путь.
- Выбираем В (7). Обновления: d(Е) через В не лучше 14 (7+7=14).
- Выбираем Д (12). Обновления: через Д к Е даёт 12+8=20, не лучше 14.
- Наконец выбираем Е (14) — нашли кратчайшее расстояние.
Путь можно восстановить по предшественникам. Один из кратчайших путей: А → Г → Е, суммарная длина 5 + 9 = 14 км. Также существует путь А → Г → Б → Е шириной 14 км, но кратчайшее расстояние остаётся 14 км.
Ответ: 14 км.
