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