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

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

Графы

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

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

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

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

Пояснение

Решение.

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

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

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

2) Рассмотрим пути, начинающиеся из A в D (длина $1$ км):
- Из D можно поехать в B: $A \to D \to B$ . Длина: $1 + 3 = 4$ км. Из B можно поехать в C: $A \to D \to B \to C$ . Длина: $4 + 3 = 7$ км. Из C есть дорога в E: $A \to D \to B \to C \to E$ . Длина: $7 + 2 = 9$ км.
- Из D можно поехать в C: $A \to D \to C$ . Длина: $1 + 3 = 4$ км. Из C есть дорога в E: $A \to D \to C \to E$ . Длина: $4 + 2 = 6$ км.
- Из D можно поехать в B, а из B в A — нельзя (повтор).

3) Проверим, есть ли другие варианты. В таблице указано, что из пункта E можно попасть только в C (длина $2$ км). Значит, любой маршрут в E обязательно должен заканчиваться участком $... \to C \to E$ .
Посмотрим кратчайший путь до C:
- $A \to B \to C$ (длина $2 + 3 = 5$ )
- $A \to D \to C$ (длина $1 + 3 = 4$ )
- $A \to B \to D \to C$ (длина $2 + 3 + 3 = 8$ )
- $A \to D \to B \to C$ (длина $1 + 3 + 3 = 7$ )

Самый короткий путь до C равен $4$ км (маршрут $A \to D \to C$ ).
Прибавляем последний участок $C \to E$ : $4 + 2 = 6$ км.

Сравним все найденные законченные маршруты до E:
1. $A \to B \to D \to C \to E$ : $10$ км.
2. $A \to D \to B \to C \to E$ : $9$ км.
3. $A \to D \to C \to E$ : $6$ км.

Минимальное значение составляет $6$ км.

Ответ: 6 км

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