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

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

Графы

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

	A	B	C	D	E
A		7	2	6	2
B	7		4
C	2	4		8
D	6		8		3
E	2			3

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

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

Пояснение

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

$A-B: 7$
$A-C: 2$
$A-D: 6$
$A-E: 2$
$B-C: 4$
$C-D: 8$
$D-E: 3$

Рассмотрим все возможные пути из пункта $B$ в пункт $D$ , учитывая условие, что каждый пункт можно посетить не более одного раза:

1) Прямого пути $B-D$ в таблице нет.

2) Путь через пункт $A$ :
$B \rightarrow A \rightarrow D$ . Длина: $7 + 6 = 13$ км.

3) Путь через пункт $C$ :
$B \rightarrow C \rightarrow D$ . Длина: $4 + 8 = 12$ км.

4) Путь через пункты $C$ и $A$ :
$B \rightarrow C \rightarrow A \rightarrow D$ . Длина: $4 + 2 + 6 = 12$ км.

5) Путь через пункты $A$ и $E$ :
$B \rightarrow A \rightarrow E \rightarrow D$ . Длина: $7 + 2 + 3 = 12$ км.

6) Путь через пункты $C$ , $A$ и $E$ :
$B \rightarrow C \rightarrow A \rightarrow E \rightarrow D$ . Длина: $4 + 2 + 2 + 3 = 11$ км.

Сравним полученные результаты: $13$ км, $12$ км, $12$ км, $12$ км и $11$ км. Самым коротким является путь $B-C-A-E-D$ , длина которого составляет $11$ км.

Ответ: 11 км

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