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