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

Решение.

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

Выпишем все доступные дороги и их длину из таблицы:
$A-B = 3$
$A-C = 3$
$B-C = 2$
$B-D = 1$
$B-E = 4$
$C-D = 5$
$D-E = 5$

Теперь рассмотрим возможные маршруты из $A$ в $D$:

1) Прямого пути $A-D$ в таблице нет.

2) Путь через пункт $B$:
$A \rightarrow B \rightarrow D$
Длина: $3 + 1 = 4$ км.

3) Путь через пункт $C$:
$A \rightarrow C \rightarrow D$
Длина: $3 + 5 = 8$ км.

4) Путь через пункты $C$ и $B$:
$A \rightarrow C \rightarrow B \rightarrow D$
Длина: $3 + 2 + 1 = 6$ км.

5) Путь через пункты $B$ и $C$:
$A \rightarrow B \rightarrow C \rightarrow D$
Длина: $3 + 2 + 5 = 10$ км.

6) Пути через пункт $E$:
Чтобы попасть в $D$ через $E$, нужно сначала доехать до $E$ из $B$.
$A \rightarrow B \rightarrow E \rightarrow D$
Длина: $3 + 4 + 5 = 12$ км.
Или через $C$: $A \rightarrow C \rightarrow B \rightarrow E \rightarrow D$, что будет еще длиннее.

Сравним полученные результаты: $4$, $8$, $6$, $10$, $12$. Самым коротким является путь $A \rightarrow B \rightarrow D$, длина которого составляет $4$ км.

Ответ: 4

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