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

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

Таблица расстояний между населёнными пунктами

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

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

3. Маршрут A→C→D имеет длину:
4+5=9

4. Маршрут A→E→D имеет длину:
6+3=9

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

6. Из рассмотренных маршрутов самым коротким является маршрут через B, C и E.