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

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

Выпишем все прямые дороги из таблицы:
$A-B = 5$
$A-C = 8$
$A-D = 8$
$A-E = 12$
$B-C = 4$
$D-B = 4$ (в таблице это пересечение строки $D$ и столбца $B$)
$D-C = 7$ (в таблице это пересечение строки $D$ и столбца $C$)
$E-C = 7$ (в таблице это пересечение строки $E$ и столбца $C$)
$E-D = 5$ (в таблице это пересечение строки $E$ и столбца $D$)

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

1) Прямой путь:
$A \rightarrow E$. Длина = $12$.

2) Пути через пункт $B$:
$A \rightarrow B \rightarrow C \rightarrow E$. Длина = $5 + 4 + 7 = 16$.
$A \rightarrow B \rightarrow D \rightarrow E$. Длина = $5 + 4 + 5 = 14$.
$A \rightarrow B \rightarrow D \rightarrow C \rightarrow E$. Длина = $5 + 4 + 7 + 7 = 23$.

3) Пути через пункт $C$:
$A \rightarrow C \rightarrow E$. Длина = $8 + 7 = 15$.
$A \rightarrow C \rightarrow B \rightarrow D \rightarrow E$. Длина = $8 + 4 + 4 + 5 = 21$.
$A \rightarrow C \rightarrow D \rightarrow E$. Длина = $8 + 7 + 5 = 20$.

4) Пути через пункт $D$:
$A \rightarrow D \rightarrow E$. Длина = $8 + 5 = 13$.
$A \rightarrow D \rightarrow B \rightarrow C \rightarrow E$. Длина = $8 + 4 + 4 + 7 = 23$.
$A \rightarrow D \rightarrow C \rightarrow E$. Длина = $8 + 7 + 7 = 22$.

Сравним все полученные результаты: $12, 16, 14, 23, 15, 21, 20, 13, 23, 22$. Минимальное значение среди них — $12$.

Ответ: 12

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