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