Решение задачи о кратчайшем пути Мышкино - Дедкино

Для решения этой задачи проанализируем таблицу расстояний между населёнными пунктами. 1. Сколько всего дорог построено между населёнными пунктами? Таблица симметрична относительно главной диагонали, так как дорога между пунктами А и Б — это та же самая дорога, что и между Б и А. Чтобы найти общее количество дорог, нужно посчитать количество заполненных ячеек только в одной половине таблицы (например, над пустой диагональю). Выпишем все уникальные дороги: \(1)\) Мышкино — Кошкино: 3 \(2)\) Мышкино — Репкино: 9 \(3)\) Кошкино — Репкино: 4 \(4)\) Кошкино — Дедкино: 5 \(5)\) Репкино — Дедкино: 2 Всего дорог: 5. 2. Вычислите длину самого короткого пути из Мышкино в Дедкино. Рассмотрим все возможные варианты проезда: Маршрут через Кошкино: Мышкино \(\to\) Кошкино \(\to\) Дедкино \[ 3 + 5 = 8 \] Маршрут через Репкино: Мышкино \(\to\) Репкино \(\to\) Дедкино \[ 9 + 2 = 11 \] Маршрут через Кошкино и Репкино: Мышкино \(\to\) Кошкино \(\to\) Репкино \(\to\) Дедкино \[ 3 + 4 + 2 = 9 \] Сравнивая полученные результаты (\(8, 11, 9\)), видим, что самый короткий путь равен 8. Ответы: Количество дорог: 5 Самый короткий путь: 8