Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 3 | 7 | 15 | ||
| B | 2 | 3 | ||||
| C | 3 | 5 | ||||
| D | 7 | 3 | 5 | 2 | 11 | |
| E | 2 | 4 | ||||
| F | 15 | 11 | 4 |
Нужно определить длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Ответ:
ОГЭ по информатике СтатГрад Вариант ИН2590101 14 октября 2025 – задание №4
Решение:
Перечислим все возможные пути из A в F без повторения вершин и найдём их длины:
- A – F: 15
- A – D – F: 7 + 11 = 18
- A – D – E – F: 7 + 2 + 4 = 13
- A – C – D – F: 3 + 5 + 11 = 19
- A – C – D – E – F: 3 + 5 + 2 + 4 = 14
- A – B – D – F: 2 + 3 + 11 = 16
- A – B – D – E – F: 2 + 3 + 2 + 4 = 11
Наименьшая длина пути равна 11 км, она достигается по маршруту:
A – B – D – E – F.
Ответ: 11