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

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

Графы

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

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

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

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

Пояснение

Решение.

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

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

2) Путь через пункт $B$ :
$A \rightarrow B \rightarrow C$ .
Длина пути: $AB + BC = 2 \text{ км} + 5 \text{ км} = 7$ км.

3) Путь через пункт $D$ :
$A \rightarrow D \rightarrow C$ .
Длина пути: $AD + DC = 4 \text{ км} + 2 \text{ км} = 6$ км.

4) Путь через пункты $B$ и $D$ :
$A \rightarrow B \rightarrow D \rightarrow C$ .
Длина пути: $AB + BD + DC = 2 \text{ км} + 1 \text{ км} + 2 \text{ км} = 5$ км.

5) Путь через пункты $D$ и $B$ :
$A \rightarrow D \rightarrow B \rightarrow C$ .
Длина пути: $AD + DB + BC = 4 \text{ км} + 1 \text{ км} + 5 \text{ км} = 10$ км.

Сравним полученные результаты: $7 \text{ км}$ , $7 \text{ км}$ , $6 \text{ км}$ , $5 \text{ км}$ и $10 \text{ км}$ . Самым коротким является путь $A \rightarrow B \rightarrow D \rightarrow C$ , длина которого составляет $5$ км.

Ответ: 5

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