Главная / Экзамен / Задание №4
Задание 4: Задача по ОГЭ информатика с таблицей дорог между населёнными пунктами A, B, C, D, E требует определить длину кратчайшего пути между A и E без повторения.
Впишите правильный ответ.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 3 | 2 | |||
| B | 4 | 5 | |||
| C | 3 | 4 | 1 | ||
| D | 2 | 1 | 4 | ||
| E | 5 | 4 |
Определите длину кратчайшего пути между пунктами A и E . Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Подсказки открываются по одной и не показывают готовый ответ.
В задаче дан граф дорог между населенными пунктами A, B, C, D и E, заданный в виде таблицы весов дорог. Нужно найти длину кратчайшего пути между пунктами A и E, при этом можно перемещаться только по указанным дорогам, а посещать каждый пункт можно один раз. Это классический графовый навык: трансформировать таблицу в граф, определить вершины и рёбра с весами и сравнить возможные маршруты. Подход к решению начинается с выделения соседей каждой вершины и рассмотрения всех простых путей без повторов, затем выбирается маршрут с минимальной суммой длин дорог. Практическая работа над задачей развивает умение читать матрицу смежности, строить ориентированно-неориентированный граф и планировать траекторию движения по графу. Такой подход полезен для понимания кратчайших путей и маршрутизации в реальных задачах.
Экза