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