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

Решение.

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

$A-B = 3$
$A-D = 2$
$B-C = 4$
$B-E = 5$
$C-D = 1$
$C-E = 4$
$D-E = 4$ (исходя из симметричности таблицы, так как на пересечении D и E стоит 4)

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

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

2) Пути через пункт $B$:
— $A \to B \to E$. Длина: $3 + 5 = 8$ км.
— $A \to B \to C \to E$. Длина: $3 + 4 + 4 = 11$ км.
— $A \to B \to C \to D \to E$. Длина: $3 + 4 + 1 + 4 = 12$ км.

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

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

Ответ: 6

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