Задание 4 ОГЭ по информатике · 672944

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

Таблица протяжённости дорог

1. Рассмотрим маршруты из A в D, проходящие только по указанным дорогам и не повторяющие пункты.

2. Маршрут A—B—C—E—D имеет длину:
3+1+1+3=8

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