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

Решение. Для решения этой задачи мы построим дерево всех возможных путей из пункта $A$ в пункт $C$, учитывая условие, что в каждый пункт можно заходить только один раз. Это поможет нам наглядно сравнить длины маршрутов и найти кратчайший.

Выпишем все возможные маршруты, начиная из пункта $A$:

1. Прямого пути из $A$ в $C$ в таблице нет (ячейка пуста). Значит, нужно искать маршруты через промежуточные пункты.

2. Из пункта $A$ можно поехать в $B$ (длина $2$) или в $D$ (длина $4$):

Ветка через пункт B:
— Путь $A \to B \to C$. Длина: $2 + 3 = 5$.
— Путь $A \to B \to D \to C$. Длина: $2 + 5 + 3 = 10$.
— Путь $A \to B \to E \to D \to C$. Длина: $2 + 2 + 5 + 3 = 12$.
— Путь $A \to B \to E \to C$. Длина: $2 + 2 + 3 = 7$.

Ветка через пункт D:
— Путь $A \to D \to C$. Длина: $4 + 3 = 7$.
— Путь $A \to D \to B \to C$. Длина: $4 + 5 + 3 = 12$.
— Путь $A \to D \to E \to C$. Длина: $4 + 5 + 3 = 12$. (Здесь мы видим, что путь $D \to E$ имеет длину $5$, а $E \to C$ — $3$).

Теперь сравним все полученные результаты:
$A \to B \to C$: $5$ км
$A \to B \to E \to C$: $7$ км
$A \to D \to C$: $7$ км
Остальные маршруты значительно длиннее.

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

Ответ: 5

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