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

Решение.

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

Выпишем все возможные маршруты, следуя правилу: каждый пункт можно посетить только один раз.

1. Рассмотрим пути, идущие через пункт B:
- Путь $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$. Длина: $3 + 2 + 4 + 1 = 10$ км.
- Путь $A \rightarrow B \rightarrow E$. Длина: $3 + 8 = 11$ км.

2. Рассмотрим пути, идущие через пункт C (минуя B):
- Путь $A \rightarrow C \rightarrow B \rightarrow E$. Длина: $7 + 2 + 8 = 17$ км. (Длиннее предыдущих).
- Путь $A \rightarrow C \rightarrow D \rightarrow E$. Длина: $7 + 4 + 1 = 12$ км.

3. Проверим, есть ли другие варианты:
- Из пункта A можно попасть только в B (3 км) или C (7 км). Прямой дороги из A в D или E нет.
- Из пункта B можно попасть в A, C или E.
- Из пункта C можно попасть в A, B или D.
- Из пункта D можно попасть в C или E.
- Из пункта E можно попасть в B или D.

Сравним полученные результаты:
- $A-B-C-D-E = 10$ км
- $A-B-E = 11$ км
- $A-C-D-E = 12$ км
- $A-C-B-E = 17$ км

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

Ответ: 10

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