1
Решение: Кратчайший путь между пунктами
ЕГЭ · Информатика · Задание 1 · Графы и пути
ПовышеннаяФИПИ3D3B2cВыбор варианта≈ 3 минутыРазбор в 3 шагаОтвет сверен с ключом
Условие
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | — | 5 | 14 | 25 | |||
| B | 5 | — | 8 | ||||
| C | — | 2 | 4 | 5 | 10 | ||
| D | 14 | 8 | 2 | — | |||
| E | 4 | — | 5 | ||||
| F | 5 | — | 5 | ||||
| G | 25 | 10 | 5 | 5 | — |
Таблица протяжённости дорог
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкамРешение по шагам
3 шага1
Рассмотрим маршрут A–B–D–C–E–G.
$$5 + 8 + 2 + 4 + 5 = 24$$2
Другие возможные маршруты имеют длину не менее 24: например, A–G имеет длину 25, а A–D–C–E–G — 25.
Следовательно, кратчайший путь проходит через пункты B, D, C и E.
$$L_{\min} = 24$$Ответ
24
24
так ответ выглядит в бланкеГде здесь ошибаются
Выбрать прямую дорогу A–G длиной 25, не проверив составные маршруты.
Пропустить одну из дорог при сложении длин маршрута.
Сложить длины несуществующих дорог, обозначенных пустыми ячейками.