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