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