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