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

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

Графы

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

	A	B	C	D	E
A		1
B	1		4	2	8
C		4			4
D		2			4
E		8	4	4

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

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

Пояснение

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

Выпишем все возможные пути из пункта $A$ в пункт $E$ :

1) Прямой путь из $A$ в $E$ :
Согласно таблице, между пунктами $A$ и $E$ есть прямая дорога.
$A \rightarrow E$ . Длина пути = $8$ км.

2) Пути через пункт $B$ :
Из $A$ можно попасть в $B$ (расстояние $1$ ). Из $B$ есть дороги в $C$ , $D$ и $E$ .
— $A \rightarrow B \rightarrow E$ . Длина: $1 + 8 = 9$ км.
— $A \rightarrow B \rightarrow C \rightarrow E$ . Длина: $1 + 4 + 4 = 9$ км.
— $A \rightarrow B \rightarrow D \rightarrow E$ . Длина: $1 + 2 + 4 = 7$ км.

3) Проверим, есть ли другие варианты, проходящие через большее количество пунктов:
— $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$ . Но между $C$ и $D$ дороги нет (в таблице пусто).
— $A \rightarrow B \rightarrow D \rightarrow C \rightarrow E$ . Длина: $1 + 2 + 4 + 4 = 11$ км.

Теперь сравним длины всех найденных маршрутов:
1. $A \rightarrow E$ — $8$ км.
2. $A \rightarrow B \rightarrow E$ — $9$ км.
3. $A \rightarrow B \rightarrow C \rightarrow E$ — $9$ км.
4. $A \rightarrow B \rightarrow D \rightarrow E$ — $7$ км.
5. $A \rightarrow B \rightarrow D \rightarrow C \rightarrow E$ — $11$ км.

Самым коротким оказался путь $A \rightarrow B \rightarrow D \rightarrow E$ , его длина составляет $7$ км.

Ответ: 7

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