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

Решение.

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

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

Шаг 2. Найдём кратчайший путь из пункта $D$ в пункт $E$.
Важно помнить, что мы уже посетили пункт $A$, и возвращаться в него нельзя.
1) Прямой путь: $D \to E$. Его длина равна $5$.
2) Через пункт $C$: $D \to C \to E$. Длина: $2 + 2 = 4$.
3) Через пункт $B$: $D \to B \to E$. Длина: $3 + (\text{нет дороги } B \text{-} E)$ — не подходит.
Самый короткий путь от $D$ до $E$ — это путь через пункт $C$ ($D \to C \to E$) длиной $4$.

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

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

Таким образом, кратчайший путь: $A \to D \to C \to E$.

Ответ: 10

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