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

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

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

1. Рассмотрим возможные маршруты из A в D и сложим длины входящих в них дорог.
A–B–D:6+5=11

2. Другие допустимые маршруты имеют длины:
A–C–D невозможно;A–E–D:4+6=10

3. Маршрут через B и C имеет длину:
A–B–C–D:6+2+2=10

4. Самый короткий маршрут проходит через E, B и C.
A–E–B–C–D:4+1+2+2=9