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

Решение.

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

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

1) Прямой путь A — E:
Согласно таблице, между пунктами A и E есть прямая дорога. Её длина равна $1$ км.
Однако, внимательно изучив таблицу, мы видим, что на пересечении строки A и столбца E стоит число $1$. Но давайте проверим остальные связи, так как в задачах ОГЭ часто требуется рассмотреть все варианты.

Внимание: Перепроверим данные таблицы.
A связана с: B ($2$), C ($5$), D ($1$).
B связана с: A ($2$), C ($3$).
C связана с: A ($5$), B ($3$), D ($3$), E ($2$).
D связана с: A ($1$), C ($3$).
E связана с: C ($2$).

Заметим важную деталь: пункт E напрямую связан только с пунктом C. В столбце E (или строке E) стоит только одно число — $2$ на пересечении с пунктом C. Это значит, что любой путь в пункт E обязательно должен проходить через пункт C.

Теперь найдём кратчайший путь из A в C и прибавим к нему длину дороги C — E ($2$ км):

2) Путь A — C — E:
Длина = $AC + CE = 5 + 2 = 7$ км.

3) Путь A — B — C — E:
Длина = $AB + BC + CE = 2 + 3 + 2 = 7$ км.

4) Путь A — D — C — E:
Длина = $AD + DC + CE = 1 + 3 + 2 = 6$ км.

Других способов попасть в пункт C (а значит, и в E) без повторного посещения пунктов нет. Сравним полученные результаты: $7$ км, $7$ км и $6$ км.

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

Ответ: 6 км

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