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