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

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

Графы

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

	A	B	C	D
A		5	8	3
B	5		2	1
C	8	2		4
D	3	1	4

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

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

Пояснение

Решение.

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

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

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

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

3) Путь через пункт $D$ ( $A \rightarrow D \rightarrow C$ ):
Длина дороги $AD = 3$ км.
Длина дороги $DC = 4$ км.
Итого: $3 + 4 = 7$ км.

4) Путь через пункты $D$ и $B$ ( $A \rightarrow D \rightarrow B \rightarrow C$ ):
Длина дороги $AD = 3$ км.
Длина дороги $DB = 1$ км.
Длина дороги $BC = 2$ км.
Итого: $3 + 1 + 2 = 6$ км.

5) Путь через пункты $B$ и $D$ ( $A \rightarrow B \rightarrow D \rightarrow C$ ):
Длина дороги $AB = 5$ км.
Длина дороги $BD = 1$ км.
Длина дороги $DC = 4$ км.
Итого: $5 + 1 + 4 = 10$ км.

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

Ответ: 6

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