Задача к ЕГЭ по информатике на тему «длина кратчайшего пути между пунктами (только таблица)» №1

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

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


	$A$	$B$	$C$	$D$	$E$	$F$	$G$

$A$		2		6

$B$	2		5	3

$C$		5		1			8

$D$	6	3	1		9	7

$E$				9			5

$F$				7			7

$G$			8		5	7

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

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут:

$A − B − D − C − G$ . Его длина равна $2+ 3+ 1 +8 = 14$ .

Стоит отметить, что изменение маршрута приведет к увеличению количества слагаемых и их сумме.

Ответ: 14

Длина кратчайшего пути между пунктами (только таблица)