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