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

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

Графы

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

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

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

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

Пояснение

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

Сначала выпишем прямые связи из таблицы:
A связан с: B (2 км), C (3 км), D (4 км).
B связан с: A (2 км), C (1 км), D (5 км), E (2 км).
C связан с: A (3 км), B (1 км), E (5 км).
D связан с: A (4 км), B (5 км), E (7 км).
E связан с: B (2 км), C (5 км), D (7 км).

Теперь рассмотрим все возможные маршруты из A в E:

1. Пути через пункт B:
— $A \to B \to E$ . Длина: $2 + 2 = 4$ км.
— $A \to B \to C \to E$ . Длина: $2 + 1 + 5 = 8$ км.
— $A \to B \to D \to E$ . Длина: $2 + 5 + 7 = 14$ км.

2. Пути через пункт C:
— $A \to C \to E$ . Длина: $3 + 5 = 8$ км.
— $A \to C \to B \to E$ . Длина: $3 + 1 + 2 = 6$ км.
— $A \to C \to B \to D \to E$ . Длина: $3 + 1 + 5 + 7 = 16$ км.

3. Пути через пункт D:
— $A \to D \to E$ . Длина: $4 + 7 = 11$ км.
— $A \to D \to B \to E$ . Длина: $4 + 5 + 2 = 11$ км.
— $A \to D \to B \to C \to E$ . Длина: $4 + 5 + 1 + 5 = 15$ км.

Сравним полученные результаты: 4, 8, 14, 8, 6, 16, 11, 11, 15. Самым коротким является путь $A \to B \to E$ , длина которого составляет $4$ км.

Ответ: 4

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