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

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

Графы

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

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

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

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

Пояснение

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

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

1) Рассмотрим пути, начинающиеся с дороги $A \rightarrow B$ (длина 4):
— $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$ . Длина: $4 + 1 + 3 + 1 = 9$ .
— $A \rightarrow B \rightarrow D \rightarrow E$ . Длина: $4 + 5 + 1 = 10$ .
— $A \rightarrow B \rightarrow D \rightarrow C$ . Путь не ведет в $E$ , а из $C$ в $E$ прямой дороги нет.

2) Рассмотрим пути, начинающиеся с дороги $A \rightarrow C$ (длина 7):
— $A \rightarrow C \rightarrow B \rightarrow D \rightarrow E$ . Длина: $7 + 1 + 5 + 1 = 14$ .
— $A \rightarrow C \rightarrow D \rightarrow E$ . Длина: $7 + 3 + 1 = 11$ .

3) Проверим, есть ли другие варианты. Из пункта $A$ выходят только две дороги: в $B$ и в $C$ . Все возможные продолжения этих путей, ведущие к конечному пункту $E$ , мы рассмотрели выше.

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

Минимальное значение среди найденных путей равно $9$ .

Ответ: 9

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