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

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

1. Из пункта $A$ мы можем попасть в:
— $B$ (длина $2$);
— $C$ (длина $5$);
— $F$ (длина $15$). Это прямой путь $A \to F$, его длина равна $15$ км.

2. Рассмотрим маршруты через пункт $B$:
Из $B$ можно попасть в $C$ (длина $1$).
Получаем путь $A \to B \to C$. Его длина: $2 + 1 = 3$ км.
Из $C$ теперь можно пойти в $D$ (длина $1$) или в $E$ (длина $3$).
— Если идем в $D$: $A \to B \to C \to D$ (длина $3 + 1 = 4$ км). Из $D$ можно попасть в $F$ (длина $6$). Итого путь $A \to B \to C \to D \to F$ равен $4 + 6 = 10$ км.
— Если идем в $E$: $A \to B \to C \to E$ (длина $3 + 3 = 6$ км). Из $E$ можно попасть в $F$ (длина $3$). Итого путь $A \to B \to C \to E \to F$ равен $6 + 3 = 9$ км.

3. Рассмотрим маршруты через пункт $C$ напрямую из $A$:
Путь $A \to C$ имеет длину $5$ км.
— Если идем в $D$: $A \to C \to D \to F$. Длина: $5 + 1 + 6 = 12$ км.
— Если идем в $E$: $A \to C \to E \to F$. Длина: $5 + 3 + 3 = 11$ км.
— Если идем в $B$: $A \to C \to B$. Но из $B$ дорог в новые пункты (кроме уже посещенных $A$ и $C$) нет.

4. Сравним все найденные варианты:
— $A \to F = 15$ км;
— $A \to B \to C \to D \to F = 10$ км;
— $A \to B \to C \to E \to F = 9$ км;
— $A \to C \to D \to F = 12$ км;
— $A \to C \to E \to F = 11$ км.

Самым коротким оказался путь $A \to B \to C \to E \to F$, длина которого составляет $9$ км.

Ответ: 9 км.

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