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

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

Посмотрим на таблицу и выпишем прямые дороги из пункта $A$:
1. Из $A$ в $B$ — длина $2$ км.
2. Из $A$ в $C$ — длина $1$ км.
3. Из $A$ в $D$ — длина $4$ км.
4. Из $A$ в $E$ — длина $8$ км. (Это наш первый возможный маршрут, его длина $8$ км).

Теперь проверим, нет ли более коротких путей через промежуточные пункты:

Рассмотрим пути через пункт $B$:
Из $B$ можно поехать в $E$ напрямую.
Путь $A \to B \to E$: длина $2 + 5 = 7$ км. (Это короче, чем $8$ км).

Рассмотрим пути через пункт $C$:
Из $C$ есть дорога в $D$.
Путь $A \to C \to D$: длина $1 + 2 = 3$ км.
Теперь из $D$ можно поехать в $E$:
Путь $A \to C \to D \to E$: длина $1 + 2 + 3 = 6$ км. (Это ещё короче).

Проверим другие варианты:
Путь $A \to D \to E$: длина $4 + 3 = 7$ км.
Путь $A \to B \to C \to D \to E$: в таблице нет прямой дороги из $B$ в $C$, поэтому такой маршрут невозможен.
Путь $A \to C \to B \to E$: в таблице нет прямой дороги из $C$ в $B$, такой маршрут невозможен.

Сравним все найденные результаты:
1. $A \to E = 8$ км.
2. $A \to B \to E = 7$ км.
3. $A \to D \to E = 7$ км.
4. $A \to C \to D \to E = 6$ км.

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

Ответ: 6 км

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