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

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

Выпишем все возможные пути из пункта B:

1. Путь через A:
Из B можно поехать в A (длина $6$).
- Из A можно поехать в D (длина $1$). Из D можно поехать в E (длина $6$).
Итого путь B — A — D — E: $6 + 1 + 6 = 13$ км.
- Из A можно поехать в E напрямую (длина $4$).
Итого путь B — A — E: $6 + 4 = 10$ км.

2. Путь через C:
Из B можно поехать в C (длина $2$).
- Из C можно поехать в D (длина $2$). Из D можно поехать в E (длина $6$).
Итого путь B — C — D — E: $2 + 2 + 6 = 10$ км.
- Из C можно поехать в D (длина $2$), а из D в A (длина $1$), а из A в E (длина $4$).
Итого путь B — C — D — A — E: $2 + 2 + 1 + 4 = 9$ км.

3. Путь через D:
Из B можно поехать в D (длина $5$).
- Из D можно поехать в E напрямую (длина $6$).
Итого путь B — D — E: $5 + 6 = 11$ км.
- Из D можно поехать в A (длина $1$), а из A в E (длина $4$).
Итого путь B — D — A — E: $5 + 1 + 4 = 10$ км.
- Из D можно поехать в C (длина $2$). Но из C дорог в E, кроме как через уже посещённые пункты B и D, нет.

Сравним полученные результаты:
B — A — D — E: $13$ км
B — A — E: $10$ км
B — C — D — E: $10$ км
B — C — D — A — E: $9$ км
B — D — E: $11$ км
B — D — A — E: $10$ км

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

Ответ: 9 км

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