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

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


	A	B	C	D	E	F

A		3	4			18

B	3		3

C	4	3		4

D			4		2	6

E				2		1

F	18			6	1

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

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

$A → F = 18$

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

$A → C → D → F = 4+ 4+ 6 = 14$

$A → C → D → E → F = 4+ 4 + 2+ 1 = 11$

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

Ответ: 11