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