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