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

#55796Задание №4ФИПИ

Графы

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	E
A		2			3
B	2		5	2	4
C		5		1
D		2	1
E	3	4

Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Правильный ответ

Пояснение

Решение.

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

1) Рассмотрим прямые дороги из пункта A:
Из пункта A можно попасть в B (длина $2$ ) и в E (длина $3$ ).

2) Разберем пути, идущие через пункт B:
- Путь $A \to B \to D$ . Длина: $2 + 2 = 4$ .
- Путь $A \to B \to C$ . Из C можно пойти в D. Получаем путь $A \to B \to C \to D$ . Длина: $2 + 5 + 1 = 8$ .
- Путь $A \to B \to E$ . Из E дорог в D нет (кроме возврата в B, что запрещено). Этот путь не ведет к цели.

3) Разберем пути, идущие через пункт E:
- Путь $A \to E \to B$ . Из B можно пойти в D. Получаем путь $A \to E \to B \to D$ . Длина: $3 + 4 + 2 = 9$ .
- Путь $A \to E \to B \to C \to D$ . Длина: $3 + 4 + 5 + 1 = 13$ .

4) Сравним длины всех найденных маршрутов:
- $A \to B \to D$ : $4$ км.
- $A \to B \to C \to D$ : $8$ км.
- $A \to E \to B \to D$ : $9$ км.
- $A \to E \to B \to C \to D$ : $13$ км.

Самым коротким оказался путь $A \to B \to D$ , его протяженность составляет $4$ км.

Ответ: 4

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