Задание №4 — Теоретические основы информатики

Решение.

Для решения этой задачи мы построим дерево всех возможных путей из пункта $A$ в пункт $E$, чтобы найти самый короткий из них. В таблице указаны расстояния между пунктами: если на пересечении строки и столбца стоит число, значит, между этими пунктами есть прямая дорога.

Выпишем все возможные маршруты, следуя правилу: в одном пути нельзя посещать один и тот же пункт дважды.

1) Рассмотрим пути, начинающиеся с прямой дороги $A \to B$ (длина $2$):
— Из $B$ можно поехать в $C$ (длина $1$). Получаем путь $A \to B \to C$. Из $C$ есть дорога в $E$ (длина $2$).
Путь $A \to B \to C \to E$. Длина: $2 + 1 + 2 = 5$.
— Из $C$ также можно поехать в $D$ (длина $3$), но из $D$ дорог в $E$ нет (только обратно в $A$ или $C$).

2) Рассмотрим пути, начинающиеся с прямой дороги $A \to C$ (длина $5$):
— Из $C$ можно сразу поехать в $E$ (длина $2$).
Путь $A \to C \to E$. Длина: $5 + 2 = 7$.
— Из $C$ можно поехать в $B$ (длина $1$), но из $B$ дороги ведут только в $A$ и $C$, где мы уже были.

3) Рассмотрим пути, начинающиеся с прямой дороги $A \to D$ (длина $1$):
— Из $D$ можно поехать в $C$ (длина $3$). Получаем путь $A \to D \to C$. Из $C$ едем в $E$ (длина $2$).
Путь $A \to D \to C \to E$. Длина: $1 + 3 + 2 = 6$.
— Из $C$ можно поехать в $B$ (длина $1$), но это только удлинит путь и не приведет к новым вариантам до $E$.

Сравним длины найденных маршрутов:
1. $A \to B \to C \to E$: $5$ км.
2. $A \to C \to E$: $7$ км.
3. $A \to D \to C \to E$: $6$ км.

Самым коротким является путь $A \to B \to C \to E$, его длина составляет $5$ км.

Ответ: 5

Источник: ФИПИ