Задача к ОГЭ по информатике на тему «Анализ таблицы» №7

Просмотров 6 Комментарии 0

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


	A	B	C	D	E	F

A		3	1	2	6

B	3		1

C	1	1

D	2				2

E	6			2		3

F					3

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

Рассмотрим различные варианты маршрута из пункта B в пункт F:

$B → C → A → E → F = 1+ 1 + 6+ 3 = 11$

$B → A → E → F = 3+ 6+ 3 = 12$

$B → C → A → D → E → F = 1+ 1+ 2 +2 + 3 = 9$

Получаем, что длина кратчайшего пути равна 9.

Ответ: 9