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

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

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

2. Рассмотрим продолжение пути из пункта B (уже пройдено $3$ км):
— В C (длина $1$ км). Итого путь A-B-C: $3 + 1 = 4$ км.
— В A возвращаться нельзя по условию задачи.

3. Теперь рассмотрим пути из пункта C. Мы можем попасть в него напрямую из A (длина $5$) или через B (длина $4$). Выгоднее идти через B.
Из C (путь A-B-C, длина $4$) можно пойти:
— В D (длина $2$ км). Итого путь A-B-C-D: $4 + 2 = 6$ км.
— В B и A возвращаться нельзя.

4. Рассмотрим продолжение пути из пункта D (путь A-B-C-D, длина $6$):
— В E (длина $4$ км). Итого путь A-B-C-D-E: $6 + 4 = 10$ км.
— В F (длина $6$ км). Итого путь A-B-C-D-F: $6 + 6 = 12$ км.

5. Рассмотрим продолжение пути из пункта E (путь A-B-C-D-E, длина $10$):
— В F (длина $1$ км). Итого путь A-B-C-D-E-F: $10 + 1 = 11$ км.
— В D возвращаться нельзя.

6. Сравним все найденные маршруты до пункта F:
— A-F: $15$ км
— A-B-C-D-F: $12$ км
— A-B-C-D-E-F: $11$ км

Другие варианты (например, через прямую дорогу A-C) будут заведомо длиннее, так как путь A-C ($5$ км) длиннее, чем A-B-C ($4$ км).

Таким образом, кратчайший путь равен $11$ км.

Ответ: 11

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