Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Каждый пункт можно посетить только один раз.
Ответ:
Демонстрационный вариант ОГЭ 2026 по информатике задание №4
Решение:
Даны дороги (км):
- A–B = 2
- A–C = 4
- A–E = 6
- B–C = 1
- C–D = 5
- C–E = 1
- D–E = 3
Нужно найти кратчайший путь из A в D, проходя по каждой вершине не более одного раза.
Рассмотрим возможные маршруты:
- A – C – D: 4 + 5 = 9
- A – E – D: 6 + 3 = 9
- A – B – C – D: 2 + 1 + 5 = 8
- A – C – E – D: 4 + 1 + 3 = 8
- A – B – C – E – D: 2 + 1 + 1 + 3 = 7
Кратчайший из этих путей — A – B – C – E – D с длиной 7 км.
Ответ: 7