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

Решение.

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

Выпишем все доступные дороги и их длины:
$A-B = 1$
$A-C = 1$
$A-E = 2$
$B-C = 3$
$B-D = 6$
$C-D = 1$
$D-E = 7$

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

1) Прямого пути $A-D$ в таблице нет.
2) Путь через пункт $B$:
$A \to B \to D$. Длина: $1 + 6 = 7$.
3) Путь через пункт $C$:
$A \to C \to D$. Длина: $1 + 1 = 2$.
4) Путь через пункты $B$ и $C$:
$A \to B \to C \to D$. Длина: $1 + 3 + 1 = 5$.
5) Путь через пункты $C$ и $B$:
$A \to C \to B \to D$. Длина: $1 + 3 + 6 = 10$.
6) Путь через пункт $E$:
$A \to E \to D$. Длина: $2 + 7 = 9$.

Сравним полученные результаты: $7, 2, 5, 10, 9$. Самым коротким является путь $A \to C \to D$, его длина равна $2$.

Ответ: 2

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