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

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

Выпишем все возможные связи между пунктами, исходя из таблицы:
A связан с B ($5$ км) и C ($3$ км).
B связан с A ($5$ км), C ($1$ км) и D ($4$ км).
C связан с A ($3$ км), B ($1$ км) и D ($6$ км).
D связан с B ($4$ км), C ($6$ км) и E ($1$ км).
E связан с D ($1$ км).

Теперь проследим все пути из пункта A в пункт E:

1. Пути, начинающиеся с A → B:
• A → B → D → E. Длина пути: $5 + 4 + 1 = 10$ км.
• A → B → C → D → E. Длина пути: $5 + 1 + 6 + 1 = 13$ км.

2. Пути, начинающиеся с A → C:
• A → C → D → E. Длина пути: $3 + 6 + 1 = 10$ км.
• A → C → B → D → E. Длина пути: $3 + 1 + 4 + 1 = 9$ км.

Сравним полученные результаты:
1) Путь A-B-D-E: $10$ км.
2) Путь A-B-C-D-E: $13$ км.
3) Путь A-C-D-E: $10$ км.
4) Путь A-C-B-D-E: $9$ км.

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

Ответ: 9 км

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