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

Решение. Для решения этой задачи мы выпишем все возможные маршруты из пункта D в пункт B, проходя через промежуточные населённые пункты. По условию задачи каждый пункт можно посетить только один раз.

Сначала выпишем прямые дороги и связи, указанные в таблице:
Из пункта D можно попасть в:
— A (длина $5$ км)
— C (длина $6$ км)
— E (длина $2$ км)

Теперь рассмотрим все возможные пути от D до B, используя эти направления:

1) Путь через A:
— D → A → B. Длина: $5 + 6 = 11$ км.
— D → A → C → B. Длина: $5 + 1 + 4 = 10$ км.
— D → A → E → B. В таблице нет прямой дороги из E в B, но есть дорога из E в A. Однако мы уже в A, а посещать пункты дважды нельзя. Проверим другие варианты.

2) Путь через C:
— D → C → B. Длина: $6 + 4 = 10$ км.
— D → C → A → B. Длина: $6 + 1 + 6 = 13$ км.

3) Путь через E:
— D → E → A → B. Длина: $2 + 2 + 6 = 10$ км.
— D → E → A → C → B. Длина: $2 + 2 + 1 + 4 = 9$ км.

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

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

Ответ: 9

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