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

Решение.

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

Шаг 1. Находим кратчайший путь из пункта $A$ в пункт $D$.
Посмотрим на таблицу и выпишем возможные варианты путей из $A$ в $D$:
1) Прямой путь: $A \to D = 8$.
2) Через пункт $B$: $A \to B \to D$. Длина: $3 + 4 = 7$.
3) Через пункт $C$: $A \to C \to D$. Длина: $9 + 2 = 11$ (это длиннее, чем прямой путь).
4) Через пункты $B$ и $C$: $A \to B \to C \to D$. В таблице нет прямой дороги из $B$ в $C$, поэтому такой путь невозможен.
Самый короткий путь из $A$ в $D$ имеет длину $7$ (маршрут $A \to B \to D$).

Шаг 2. Находим кратчайший путь из пункта $D$ в пункт $E$.
Важно помнить, что по условию задачи каждый пункт можно посетить только один раз. Пункты $A$ и $B$ мы уже использовали в первой части пути.
Рассмотрим варианты из $D$ в $E$:
1) Прямой путь: $D \to E = 5$.
2) Через пункт $C$: $D \to C \to E$. Длина: $2 + 2 = 4$.
Путь через $C$ короче, его длина равна $4$.

Шаг 3. Вычисляем итоговую длину маршрута.
Сложим длины двух найденных участков:
$L = (A \to B \to D) + (D \to C \to E)$
$L = 7 + 4 = 11$.

Проверим, нет ли других вариантов. Если мы пойдем $A \to D$ напрямую (длина $8$), то кратчайший остаток пути $D \to C \to E$ (длина $4$) даст в сумме $12$, что больше $11$. Если мы пойдем из $A$ в $D$ через $B$, а потом сразу в $E$, получим $7 + 5 = 12$, что также больше $11$.

Таким образом, кратчайший путь: $A \to B \to D \to C \to E$, его длина равна $11$.

Ответ: 11

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