ГДЗ по информатике 9 класс Босова, номер Гл.2 Т 17

Гл. Т

Кратчайший путь по таблице дорог

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

	A	B	C	D	E	F
A		9	10		3	15
B	9		2			8
C	10	2		3
D			3		3	2
E	3			3
F	15	2		2

Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, указанным в таблице.
а) 8
б) 12
в) 13
г) 15

Решение

Найдём кратчайшие расстояния от B, последовательно добавляя ближайший достижимый пункт. Из B непосредственно можно попасть в C за , в F за и в A за .

Через C можно попасть в D за . Через D достигаем E за , а F за , что короче прямой записи B–F, равной в строке B. Через A пункт E достигается за . Путь через F и D по строкам от B имеет длину . Поэтому путь B–C–D–E длиной пока лучший.

Проверим, что короче быть не может: к E ведут дороги из A и D. Наименьшая длина до D — через C, значит, через D до E нужно не менее . До A из B не менее , так что через A получится не менее . Следовательно, кратчайшая длина равна .

В таблице значение B–F равно , а F–B равно . Для пути из B использовано значение из строки B; это различие не меняет найденного кратчайшего пути.

Ответ

а) км; путь B–C–D–E.

Помогло?

Номер Гл.2 Т 17