4
Шешімі: Кратчайший путь в графе
ОГЭ · Информатика · Тапсырма 4 · Графы и пути
КүрделіФИПИ8E0617Қысқа жауап≈ 3 минутТалдау 4 қадамЖауап сверен с ключом
Условие
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых в километрах приведена в таблице. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 6 | 4 | |||
| B | 6 | 2 | 5 | 1 | |
| C | 2 | 2 | |||
| D | 5 | 2 | 6 | ||
| E | 4 | 1 | 6 |
Таблица протяжённости дорог
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
4 қадам1
Рассмотрим возможные маршруты из A в D и сложим длины входящих в них дорог.
$$A\text{–}B\text{–}D: 6+5=11$$2
Другие допустимые маршруты имеют длины:
$$A\text{–}C\text{–}D\text{ невозможно};\quad A\text{–}E\text{–}D: 4+6=10$$3
Маршрут через B и C имеет длину:
$$A\text{–}B\text{–}C\text{–}D: 6+2+2=10$$Самый короткий маршрут проходит через E, B и C.
$$A\text{–}E\text{–}B\text{–}C\text{–}D: 4+1+2+2=9$$Жауап
9
9
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывают дорогу E–B длиной 1 км.
Выбирают маршрут с меньшим числом дорог, но не с минимальной общей длиной.
Используют несуществующую дорогу между A и C.