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